I am reading Isometric Game programming with directx 7.0. I am using tile pathfinding even though my program isn''t run by tiles. Anyway, my screen resolution is 800x600. To do this for each pixel would be mind-boggeling slow! So I divide it into 5x5 squares. So far so good. Now, I only find the path when the player clicks. What I want to know is if there is a way to fill the path WHILE the character is walking, because it will sit there for a second or two finding the path! This may not seem like a lot, but for an adventure game, if I were a player, I would hate waiting for 2 seconds EACH time I wanted to move. Thanks, Sponge Factory --Muzlack

Depending on the type of terrain etc. you are using in your game, you could try using a Line-Of-Sight check in the direction of the goal (where the user clicked) to see if there are any obstacles in the way, if not, you don''t even have to run a search, because the straight line distance will be quickest (once again, depending on terrain you use). If you do encounter an obstacle, you could run A* from an arbitrary point before the obstacle to an arbitrary point after the obstacle to find the shortest path around the obstacle, then once around the obstacle, do another LOS test to the goal, and repeat etc.
Once again, i''ll say it depends on your terrain. If you simply have blocking, and non-blocking terrain it should work fine. It won''t find the shortest possible path, but should come pretty close, and in many cases the LOS check will run straight to the goal and A* won''t even have to run. However, if you happen to use terrain that is non-blocking, but slows the units down, using this system is probably not such a good idea, as it could return really stupid paths (going in a straight line through swamps, instead of walking a couple metres up the road to cross at a bridge or something).
The other thing i could suggest would be to increase your grid size. Changing from 5x5 to 10x10 should cut your search time by about 75%.

Oops, and to add to the above, if you want your units to start moving before the search is complete, allocate a certain time or depth limit to the search, and when that limit is reached, save the tree, send the units off in the direction of the currently expanded node, then come back and continue the search from where you left off, continue until you reach the goal or A* runs out of nodes and fails. (in which case you should tell your units to stop moving i guess )
Hope that helps.

I understand. But it will take a very long time to implement this

quote: Original post by Anonymous Poster
Oops, and to add to the above, if you want your units to start moving before the search is complete, allocate a certain time or depth limit to the search, and when that limit is reached, save the tree, send the units off in the direction of the currently expanded node, then come back and continue the search from where you left off, continue until you reach the goal or A* runs out of nodes and fails.

There is a serious flaw in this logic... there is absolutely no guarantee (and can never be) that the last expanded node lies on the optimal path - or even on any path - that leads from the start to the goal.

Timkin

I know, but at least your troops will start moving, and it won''t look like they''re just sitting their doing nothing after you''ve given the command. Even if they start moving in completely the wrong direction, many people would prefer (from a gameplay perspective) that they do something immediately when you give them an order, rather than just doing nothing for a few seconds while it calculates the path. Another option as far as this goes, is instead of starting them moving when you give them an order, they could spend a certain amount of time (the time it takes to computer the A* search) "getting ready" to move. For instance, they might spend some time moving into formation, or readying their weapons etc. Just something to let the player know that their input worked...

Just use much bigger grid and then smooth the path with bezier curves. Dunno how detailed the environment is but I'd probably use something like 16x16 grid.

If the environment is static and not too complex (I assume so because it's an adventure game), you could precalculate a few waypoints and then use A* for these waypoints.

[edited by - civguy on April 17, 2002 3:10:07 PM]