quote:Original post by strangebreed Firstly, modern games don’t use uniform grids anymore, (and probably haven’t for the last two years).
That''s a bit of a generalization! There must be hundreds of developers working on games that use (or can use) a square, diamond, or hexagonal-tiled approach.
Well, StrangeBreed, I am talking here about a uniform grid RTS. I don''t know if an arbitrary navigation mesh is applicable in a standard RTS. And I want the user to be able to create a map without having to worry about placing points.
The only use for pointers in my data structures is to point to the current stack position in each of the seven USHORT arrays of 17000 elements (the stacks) that represent my open list, so that inserting a node is very straightforward, and when the stack 0 is empty, I just rotate the seven pointers. I am a beginner C++ programmer, but I think it''s pretty efficient and straighforward.
Oh, and the BFS I was talking earlier, is not really a BFS, altough that was the original intention, but a Dijkstra, as it always finds the shortest path because it always checks the shortest cost nodes first.
quote:Original post by strangebreed Firstly, modern games don’t use uniform grids anymore, (and probably haven’t for the last two years).
That''s a bit of a generalization! There must be hundreds of developers working on games that use (or can use) a square, diamond, or hexagonal-tiled approach.
Good insight into the problem -- you need to implement a priority queue, and taking advantage of the cost between tiles being a small integer means that you can implement a more efficient priority queue. Try searching the web for HOT Queues for a generalization of your idea that can handle more than a few small integer costs.
I don''t know whether it helps in practice, but it''s worth a try.
You might want to have your A* implementation go through a priority queue interface instead of hard-coding any particular priority queue. That way, you can plug in different priority queues (your multiple queue idea, the standard sorted linked list, binary heap, sorted array, etc.) and measure performance and correctness.
-- Amit (http://www-cs-students.stanford.edu/~amitp/gameprog.html)
