Implementing better recursive pathfinding in isometric map?

which method are you using, last week I implemented A* (A Star) using the method described here, although I didnt used his code, I implemented a couple of functions using his pseudocode and STL deques that work very well for me.

with a staggered map, a depth-first search becomes something of a problem because of the layout of the map itself. one thing you might try is to convert from the staggered map coordinates to diamond map coordinates, and THEN do your depth first search.

hmmm,
actually its not really a DFS nor BFS, its a Priority BFS.
my question was, for those who didnt understand, is what priority
should i give to each square?

like the "price" of the road in A* algorithem.
my problem is that i cant find the equation that
will give me natural walking.

Gil

typically, if the cost for a clear tile with grassland is 1, then a moving from one tile with road on it into another tile with road on it has a cost of 1/3. This is almost a standard in strategy board games.

Using finite state machines (FSM) alongside your pathfinding algorithm can help achieve natural looking movement. It just takes some brainstorming and planning to make it all come together. If you want some ideas, I can help with some of them.

Make clear defined goals - it should be more than just moving from point A to point B. For example, friend-1 is trying to make its way to enemy-1 without being killed while traveling through the wilderness. Identify the states in this scenario.

Goal: Friend-1 tracks down enemy-1.
Stance: Cautious, not wanting to get killed easily.
Setting: Wilderness.

Starting with just the goal it would seem to make it a simple case of going from point A to point B. That isn''t the case though, because of a couple of constraints on movement. First, obstacles modify your point-to-point path. Second, types of terrain may modify your path. Third, disposition or stance should also modify the path based on decisions made continously.

Some resources you might want to consider looking into are the Game Programming Gems 1 & 2 books. Book 1 has an article on FSMs, whereas, book 2 has more extensive artificial intelligence articles in section three.

- Curtiss

hmmm
so so far my cost func is:

(distance of tile from the dest tile)*(tile type in lookup i.e. road and stuff)

i know ill have to test it, but the more i add variables,
its harder to make the "cost" calculation...
i know ill have to make some tests, i just thought there are
some existing (published) ones

Gil

Well, if you get A* working, then there''s a couple simple ways to may the paths look more realistic.
Check the article on Gamasutra "Towards More Realistic Pathfinding" (I think) ''tis fairly recent.
But one simple way is to weight tiles in the direction you''re facing less, i.e. give a small amount of cost to turning. This will lead to longer straight sections which looks more realistic.

cheers,
-m

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

actually, what youre suggesting will produce what i have now:
when i give my unit a dest in like 30 deg, i get :

------------------*
-----------------*
----------------*
*************

see? less turns, but unrealistic way

Gil

p.s.
i didnt compute it that way,
i used the
a^2 + b^2 = c^2
or
grade = sqrt(deltax^2 + deltay^2)
thats what i got.

EDIT: it doesnt get spaces in my way diagram, ive put "-" instead

Edited by - GilZu on October 10, 2001 5:18:58 PM

Edited by - GilZu on October 10, 2001 5:19:47 PM

Edited by - GilZu on October 10, 2001 5:20:06 PM

Well, if you''re units actually rotate to face their direction I find that to look better than the staggered look you get otherwhise, but here''s how to "fix" it.

Calculate you''re path weighted like this. In the path store each point point at which the unit must change facing.

.........*......c
.........*...../
.....*****..../
............./
a-----------b

(* are obstacles)
Paths become face e move 10 face northeast move 5 etc....

You actually want to get the straight line from a to c

So traverse backwards from c to b. At each tile you shoot a ray to a using Bresenham''s and checking for colision. Once it succeed you move b to that point. Calculate the angle and save the path.

so you end up with, which while not perfect is a lot better.

.........*......c
.........*...../.
.....*****----b..
.....-----.......
a----............
.................

I don''t know how complex you''re world is, but one thing to remember is that obstacle avoidance has many simpler solutions than pathfinding or maze traversal.

On thing to do is to shoot a ray from start to end check for collision and only do actuall pathing if that fails.

Of course this is assuming non-weighted movement costs, i.e. a tile is either only walkable or not. One could still to the ray, calculate the cost of moving straight line and then only search if a) it''s far costlier than the theoretical "best" path or you know theres a road in the area, i.e. if unit or destination is on or next to a road us a*, or even if the ray crosses a road.

This assumes that a) walking in a straight line looks more realistic than not b) walking on roads looks more reastic than not.

enough rambling,












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