For the last couple weeks, I have been working on and off on an Real Time Strategy engine, with the final goal to be the creation of a fully featured RTS game for the calculator.  It has been quite a struggle with different types of data structures, but a lot of progress has been made since its inception.  I was reluctant to post this on the forums for a while due to it being such a large project, and because I has having such difficulty getting some of the foundations of the engine working.  However, just today I have solidified the basics of the engine.

However, the worries of this project being too much to handle for just one person still remain, so I am proposing that this be a completely open source project from the start.  This will not be a community project though, as I will still be doing most of the coding.  The idea is that from the start, anybody who is interested can take a look at the code and propose changes or optimizations as the development cycle goes on. Furthermore, I will not just be uploading the source, but simply zipping my entire development folder for all to see, so you will get to see all past backups, screenshots, and development notes that I create for myself.

The engine itself is one of the most complex I have ever written, and is still only in it's infancy.  It is being written with multiplayer in mind, so transitioning into link-play should not be difficult.  Link play will most likely come before any type of official AI, although both are planned (hoped for).  Currently the engine has these features:
 -64 units per player.  Each unit is 4x4 pixels
 -64x64 tilemap.  Each tile is 4x4 pixels, but all buildings take up an 8x8 space
 -256 4x4 'chunks' that are used in internal processing
 -Rudimentary pathing

The chunk system is the thing I have been working on for the past couple days, and it is finally working to my satisfaction.  Each player has a 832 byte section of memory allocated to all their units.  This consists of a 256 byte lookup table, and then 9 sets of 64 byte lists, each list for a different attribute.  The data structure that I chose is a linked list, and each chunk is it's own linked list.  The 256 byte lookup table has 1 byte for each chunk, and this byte points to a single object that exists within the chunk (or nowhere if there is no unit in that chunk).  Each unit then points to the next unit in the chunk, or nowhere if this is the last unit.  I have routines for adding units into the world, deleting from the world, and moving from 1 chunk to another, and they are all very efficient.  The deletion routine is just 2 simple lines, and the movement routine is equally simple.  Both moving and deletion run in constant time, while addition runs in linear time (although still very quickly). 

The pathing system is also a piece of code that was very time consuming to get working.  It is quite complicated, but I will go over the basics here.  When you order a select number of units to move to a specific location, the program does a depth fill from the destination location through the map until it locates all units (or until it has searched the whole map).  After this depth map, it generates a movement tree that all objects follow in order to get to the destination location.  Right now the way that this pathing tree is followed is very simple and often results in some traffic jams, but it is going to be improved in the future.

Anyways, that is all for now, I will leave you with a screenshot of all current progress, showcasing the unit selection and pathing routines.  I will also be uploading the development files for all to see, so enjoy!

For those of you who want to compile the latest version, you will want to go into the backups folder, choose the most recent version, and compile prgmAARTS.  Use the arrow keys to move the cursor, 2nd to select a region, alpha to toggle tiles, and Y= to send selected units to a location.

how will you distinguish between your army and enemy's army? and how many different types of units will there be? Because 4x4 seems to be pretty limited for spriting

Good luck. Your data structure sounds solid: a good foundation to build on

How are you approaching the pathing now, and how do you plan to approach it in the final game?

Edit: I guess my question is, how are you approaching the issues with coordinated pathing?

How are you approaching the pathing now, and how do you plan to approach it in the final game?

Edit: I guess my question is, how are you approaching the issues with coordinated pathing?

Well, currently that is one of the largest challenges.  Right now each unit is trying to get to the destination with no consideration for the units around it.  This causes a lot of units running into each other and geeneral sadness.  Me and Runer are working together to get this working, but currently I am trying to see if giving units a formation 'goal' that they want to attain might be the way to go.

And aeTIos the source contains 3 different files that are used in the pathing routine.
-PCALCOFF-  Calculates the offsets that are given to each unit and initializes the routine data
-PATHFIND-  Generates the depth field
-PBLDTREE-   Uses the depth field to create a pathing tree, and assigns nodes to each unit

This might be a useful tool for you to look at. I'm sure a lot of it wouldn't be entirely feasible in this game, but some of the concepts are still very valid.

http://www.gamasutra.com/view/feature/131720/coordinated_unit_movement.php

Very nice. Are those blocks not OP?

Yeah, you should probably nerf the blocks a bit.