Archived

This topic is now archived and is closed to further replies.

psjie

Real time pathfinding

Recommended Posts

Hi, i wish to create a program using c++ to show the real time pathfinding. from my research, shortest path algorithm is A* algorithm. But it''s the static searching algorithm. What pathfinding technic suitable for real-time pathfinding? what source/tutorial/lesson can i get from internet? any advice? thanks a lot!! Best Regards, from psjie

Share this post


Link to post
Share on other sites
If by "realtime" you mean large moving obstacles like a labyrinth, check out Blind Pathfinding. There are some ideas mentioned you might look into.

If you mean pathfinding that doesn''t murder your framerate, then you haven''t looked hard enough.

Share this post


Link to post
Share on other sites
A* is suitable for real-time games (used in may RTS games). Here are a few ideas to avoid killing your framerate (off the top of my head):

Use depth based pathfinding. That is, the world is divided into several layers (usually two or three). The first layer is the tile map or whatever your equivalent is. The second layer might be labelled as ''sectors'' and, as an example, each sector may be 10x10 tiles. The final layer, if you decided to include it, might be labelled as ''regions'' and each region may consist of 4x4 sectors. Then, to speed up the A* search, when determining paths split the search up. If your destination is in the same sector as your starting point then do a simple search. If not, search from the sector the starting point lies in to the sector that the destination lies in. Determine the ''next'' sector the agent will need to visit and pathfind to the centre of the sector. Then, when the centre of the sector is reached, repeat the process. Apply a similar technique when the start and destination are regions apart. Depending on the situation, this may greatly speed up the search.

Only recalculate paths when needed. This means that if you are dealing with moving objects or multiple agents that will block the movement of others, do not recalculate the path every time the agent in consideration reaches a new tile. Instead, recalculate paths when the agent detects that a blockage lies up ahead on the path by, say, four tiles. If any of the next four tiles are blocked then recalculate the path. The other thing you may like to do is ignore blockages that are moving until they are on the very next tile ahead of the agent. For instance, if the agent detects that four tiles ahead on the path there is another agent blocking, but that other agent is on the move then it is a fair bet that by the time we actually reach that tile the blocking agent will have cleared away. There will be instances where two agents may be moving toward a head on collision, in which case the one-tile-ahead thing kicks in to deal with it. In fact, if you are really concerned about performance, you might like to simply recalculate the paths only when a blockage lies on the next tile.

Limit the path calculations per frame. Here is how I have done it:
When an agent wants a path it sends a request to the pathing object. The request goes on the end of a que. Each frame the pathing object calculates a limited number of paths and sends the results back to the agents who requested them. When the pathing object comes to a request submitted by an agent who no longer exists then it is automatically skipped. The number of paths calculated per frame can then be easily altered (perhaps even give the option to the player) to get the best results. This way slower machines can set that number to, say, 1 or 2 and then have to deal with short momentarily delays while the agents wait for their path to be calculated, while faster machines can set it to unlimited and thereby utilize the full power.

Another technique is that of following a leader. That is, when moving a group of agents to a common destinations assign a leader (the slowest agent - this way the agents will move in a group) and calculate the whole path for it. Then have the other agents constantly pathfind to that leader as it moves, thereby avoiding a large number of paths being calculated at one. Personally, I never found this to be very useful, and it is probably unnecessary when you take into account the things already mentioned.

Hope this helped, although I''m not entirely sure it is what you are looking for.

Share this post


Link to post
Share on other sites