Structure of an RTS Engine
Author
So I'm trying out building an RTS engine - nothing snazzy to start with, just something simple, and I'm representing it using really simple 2D graphics for now (I'll focus on the prettiness once I've got the mechanics of the game working).
I'm doing it in C# but I'll avoid using too much C#-specific lingo so that anybody can help me with this.
Currently, the "world" - i.e. a game with players, units, buildings, etc, is represented as an object which contains a List of "WorldObjects" which be anything from Vehicles to Infantry to Buildings to general props like Trees and Rocks. Each WorldObject has a position on the map, so with each game cycle the graphics engine simply looks at each WorldObject and draws it based on its position.
I'm going to try implementing the A* algorithm for pathfinding of Units, and so I have a couple of questions (I don't expect these to be directly answered, just some advice regarding my concerns would be helpful please :) )
- Should I be representing the world as a 2-dimensional array of WorldObjects, where each square has a reference to whatever object is occupying it? This would mean, each game cycle, clearing squares and then updating them, and it would mean each unit having a reference to the larger world in order to do so - unless it used the List to do this, in which case it makes the array redundant.
- What happens if during the path chosen originally is now blocked? Should the pathfinding algorithm run again, or should a unit stop until it's no longer blocked? Should there be alternatives already lined up in the event of a blockage?
Thanks :)
a 2D array would work well (fast traversal)
Your 2nd question is the tricky one I think. Ever wonder why people talk about why AI taking up so much resources? This is one of those reasons. If it was as easy as getting the path once and going with it until the game ends, it wouldn't be that bad.
I guess the question is.. how smart do you want your unit to be and how much resources do you have to devote to your unit's intellegence.
I would suggest something like, calculate the path, then go untill your unit can detect that it has been dynamicly obstructed and recalculate a new path.
Your FPS will take a hit doing this unless your using some sort of timestep management techniques for your functions or multiple threads.
Your 2nd question is the tricky one I think. Ever wonder why people talk about why AI taking up so much resources? This is one of those reasons. If it was as easy as getting the path once and going with it until the game ends, it wouldn't be that bad.
I guess the question is.. how smart do you want your unit to be and how much resources do you have to devote to your unit's intellegence.
I would suggest something like, calculate the path, then go untill your unit can detect that it has been dynamicly obstructed and recalculate a new path.
Your FPS will take a hit doing this unless your using some sort of timestep management techniques for your functions or multiple threads.
One solution to your path finding would be perhaps to create a worker thread to calculate paths for objects. When an object needs a path it makes a request for one (add it into a queue) the worker thread then simply loops taking the request from the top of the queue and calculating the path, objects wait until they have their path then follow it. As for calculating dynamic bath blockages your objects could be moving along the path and always checking a few cells ahead to see if it is blocked, if the unit detects it is blocked a new path will be requested, and hopefully returned before the unit hits th eblockage and has to stop.
Thought I'd reply to this even if the thread is a little old now. [smile]
Use multi-resolution grids: Divide the map into 'sectors' (or 'way-points') where each sector is made up from a number of higher resolution cells, say 9x9 cells to one sector. Plan an approximate route by finding a path through the sectors first, this path is going to be more stable as it is less probable that an entire sector will become impassable. Finding the actual cell-level route to take is then just a problem of getting from the unit's current position to somewhere within the next sector of the sector-path, this is a much shorter path to find and it's one that can be re-found much faster if the unit gets blocked.
Use the D* algorithm instead of A*, it can be more efficient when the search space is unknown, or dynamic.
Quote:Original post by FragstaThat would certainly be one reasonable method; the question is for whom is this representation intended? It may be the case that different subsystems need different views of the same world, requiring different data structures. For pathfinding a grid view is often used though.
- Should I be representing the world as a 2-dimensional array of WorldObjects, where each square has a reference to whatever object is occupying it?
Quote:This would mean, each game cycle, clearing squares and then updating them, and it would mean each unit having a reference to the larger world in order to do soThe units themselves wouldn't be updating the world, the units are selfish and only care about themselves - whether or not the world state has been kept up to date isn't their concern.
Quote:- unless it used the List to do this, in which case it makes the array redundant.You probably won't need both the list view and the grid view for the same world, they're both simple structures and can pretty much be used in place of one another.
Quote:- What happens if during the path chosen originally is now blocked? Should the pathfinding algorithm run again, or should a unit stop until it's no longer blocked? Should there be alternatives already lined up in the event of a blockage?Some solutions to that have already been suggested so I'll just throw some more in:
Use multi-resolution grids: Divide the map into 'sectors' (or 'way-points') where each sector is made up from a number of higher resolution cells, say 9x9 cells to one sector. Plan an approximate route by finding a path through the sectors first, this path is going to be more stable as it is less probable that an entire sector will become impassable. Finding the actual cell-level route to take is then just a problem of getting from the unit's current position to somewhere within the next sector of the sector-path, this is a much shorter path to find and it's one that can be re-found much faster if the unit gets blocked.
Use the D* algorithm instead of A*, it can be more efficient when the search space is unknown, or dynamic.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
