I’ve come to some sort of block on my strategy game. I’ve had plenty of time to work on it in the past few days, but instead I’ve been just watching TV and stuff like that. Currently it draws a large (256×192) which has a zoomable and scrollable viewport, just like you would expect an RTS to have. It also draws a truck on the screen, which can be selected and told to go places, using a pathfinding algorithm. There are four kinds of terrain implemented: dirt, road, and shallow and deep water. What is the next step? There are several directions I could go:
- I can currently support multiple units on the screen at once, which can be separately told to go separate places. However, if their paths cross, they simply drive over each other, not acknowledging each other’s existence. I need a way for them to avoid each other. The current best algorithm I have in mind follows: each player has a list of “forbidden squares”. Whenever a unit is told to go somewhere, it marks the five seconds or so ahead of it as forbidden. Every five seconds, the pathfinding algorithm looks through its path and checks to see if it has been blocked. The forbidden squares would be seen as blocking the path, so the unit would have to go around. I should also just consider a friendly unit-unit collision to be just like a wall collision, where the engine reconsiders its path and starts again.
- None of the many things that will make this game unique has been implemented. If I wanted to start on one of those, I should start on the “formation pathfinder”, which allows you to move a group of units in formation. That is, they never take separate paths from one another and if faster units start out in back, they never drive to the front. It should be a loose formation; i.e. it should allow a little bit of variability just so it isn’t stubborn. That requires the invention of a new algorithm, or a modification to the A* I am using now. I’m thinking of using A* over the graph of possibile complete formation positions on the board; i.e. where everybody can fit in formation. The weight would be based on both the time required for the slowest unit to arrive and for how long they had to be out of formation to get there.
- There are two more pathfinding projects. The first is another thing that will make the game unique: drawing pathfinding. The user draws a curve stating roughly what path the unit should follow, and the unit does its best to follow it, maneuvering around small obsticles and the like. I’m thinking the best way to implement it is to precalculate a diffusion map over the board for the path and access it during pathfinding. I’d like to get formation pathfinding working first, though.
- The last pathfinding project is to distribute the algorithm over multiple frames. To find a path across the entire map, sometimes the algorithm will take up to a second, which is far too long to wait. The algorithm should not take up too much time, and should send the units toward its best guess when it has not completed.
- Finally, I could add some more unit types and get some guns working.