Archived

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

JaZsT

"Realistic" pathfinding....??

Recommended Posts

Hello !! So far, I have got an isometric engine with working pathfinding implemented from TAN''s book. The pathfinfing is OK as long as there are only "static blocked tiles" on the map (houses,trees,etc). But, when I add some more units on the map, the pathfinding is no longer ok, cause it allowes units to overlap. I tried to solve this problem so, that all the tiles occupied by units were marked as blocked (until units didn''t left them), but this solution is not ok. For example, the situation at the time you calculate unit''s path (when you order unit to move) is different than the situation when the unit actually reaches a certain tile --> a tile that was in the time of calculating path empty can be occupied by another unit when the selected unit actually reaches it. How do you guys do it??? Any tutorials on that topic ???? Thanx alot !! -- Uros Life lived unexplored is life not worth living !

Share this post


Link to post
Share on other sites
This is how I handle it.
I do all pathing searches without taking into account other units.
But then as a unit actually traverses it''s path it is constantly checking it''s next move to see if it can make it. If it encounters an obstacle where it should be able to move it does a couple things.
1) checks to see if the obstacle is moving and if so enters a wait state until the obstacle is no long there
2) if the object isn''t moving, it does a small path search which takes into account units from it''s current point to the next clear point on it''s previous path.
3) if for some reason this fails it does a long path search from current position to destination accounting for units and dynamics and overrides it''s previous path.
4) if no path exists except along the tile that the unit is being obstructed (usually doorways) it will actually tell the blocking unit to move off it''s path to the nearest unoccupied tile that it can reach that is not on the path.

hope this helps,
cheers,
-m




mat williams
Lead Programmer, Designer
Zero Sum Software
www.zero-sum.com

Share this post


Link to post
Share on other sites
If you want to know how the pros do it then this will save you a heap of time. But it has to be implemented in real space. Either 3D or 2D so that means using floats or doubles in C & C++ and of course vector mathematics. Forget those tile coordinates and offsets if you want to implement this.

Steering Behaviours
http://www.red3d.com/cwr/index.html

Share this post


Link to post
Share on other sites
Of course, there''s no reason why you can''t translate ''real space'' back to tiles and offsets after you''ve done the hard part of the algorithm...

tile = real_coord / TILE_SIZE;
offset = real_coord % TILE_SIZE;

etc...

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Yep thats what I do. But only when I am about to draw. If you do those translations back an forth inside your engine code it will get messy real fast.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Yep thats what I do. But only when I am about to draw. If you do those translations back an forth inside your engine code it will get messy real fast.

Share this post


Link to post
Share on other sites