quote: Original post by Timkin
Jarvis, R. A. "Collision-free trajectory planning using the distance transforms", Mechanical Engineering Transactions of the Institute of Engineers. No. 3, 1985.

You might also want to look at a 3-D version of the algorithm:

Williams, M. and Jones, D. I., "A Rapid Method for Planning Path in Three Dimensions for a Small Aerial Robot", Robotica, v19, 2001. pp125-135.

Do you know of, or have any references that are online?

Thanks,

Eric

quote: Original post by Eelco
defining landmasses is the best way to go in this situation, im quite sure.

to construct these area''s, add a member to your tile struct char area, and do a floodfill witch will fill all walkable tiles with a unique index.

If you had followed the link I posted above and looked at the Distance Transform Algorithm you would have realised (before dismissing it) that what you are suggesting is, infact, the DTA in a nutshell. The point chosen is the goal node and the value inserted into each cell is the depth of the fill from the goal node.

Geta: It appears Matthew Williams has removed his online copy of his paper. Ray Jarvis'' paper has always been hard to get a hold of... I''m not certain where I got mine... maybe directly from the department (he works at Monash). You could contact the Department of Electrical Engineering at Monash and they should be able to provide you with a copy.

I''ll check at home if I have an electronic copy of either of these papers and will forward whatever I find.

As to the other question, no I haven''t personally done a comparison of the DTA with other methods. I seem to recall Matthew''s paper considered the efficiency of the algorithm, so that might give you some pointers.

As for it''s use in games... there are several variants of the algorithm based on connectivity maps of a discrete environment. I believe some of these have been used successfully in games, although I cannot recall the references... my recollection comes from past discussions on this site.

Timkin

quote: Original post by Timkin
If you had followed the link I posted above and looked at the Distance Transform Algorithm you would have realised (before dismissing it) that what you are suggesting is, infact, the DTA in a nutshell. The point chosen is the goal node and the value inserted into each cell is the depth of the fill from the goal node.

As to the other question, no I haven''t personally done a comparison of the DTA with other methods. I seem to recall Matthew''s paper considered the efficiency of the algorithm, so that might give you some pointers.

As for it''s use in games... there are several variants of the algorithm based on connectivity maps of a discrete environment. I believe some of these have been used successfully in games, although I cannot recall the references... my recollection comes from past discussions on this site.

Timkin,

I''m trying to make a case for creating a testbed and comparing the performance of the DTA (as you described in the link you referenced above) verses the A* in a pathing performance test. One thing is, I can''t find a single reference where the DTA has been used in pathfinding. Anywhere. Since its a favorite of yours, I was hoping you had some idea of how it would perform. Other sources (and my own intuition) tell me that it is basically a floodfill (where you cost the nodes from the goal to the start) and then a hillclimber (where the DTA follows the lowest cost node from the start to the goal). And as such, an A* would probably beat it in performance.

Also, do you have a good argument for why such a comparison might be useful to game developers?

Thanks,

Eric

Timkin can probably answer this question better than I can, but I''ll give it a shot anyway. Although the combination of floodfill and hillclimber is slower than A*, the hillclimber alone should easily beat A*. Therefore DTA would be preferable in this situation:
- The goal location is relatively static
- You''ve got RAM to spare (to store the "costs map" (sorry, I don''t know the DTA jargon)

That way, you calculate the costs map once, and then use it over and over.

If P is the amount of time it takes to compute the costs map (the floodfill), H is the amount of time it takes to do the hillclimbing, N is the number of times you need to path to the goal node, and A is the amount of time it would take A* to find the same path, then DTA is preferable when...

P + NH < NA

You get the point! Now you can wait for Timkin to give you a better answer.

quote: Original post by Geta
I''m trying to make a case for creating a testbed and comparing the performance of the DTA (as you described in the link you referenced above) verses the A* in a pathing performance test. One thing is, I can''t find a single reference where the DTA has been used in pathfinding. Anywhere.

I''ll see what I can come up with for you.

quote: Original post by Geta
Other sources (and my own intuition) tell me that it is basically a floodfill (where you cost the nodes from the goal to the start) and then a hillclimber (where the DTA follows the lowest cost node from the start to the goal).

Yes, that is a fair assessment of the basic algorithm. There are variations that take into account obstacle avoidance as well (penalising locations that are close to walls and obstacles), but basically the DTA is a reverse direction breadth first search.

quote: Original post by Geta
And as such, an A* would probably beat it in performance.

Generally speaking, yes...

TF is on the right track...

A*''s performance generally rests on the ability to compute efficiently a suitable heuristic estimate. In many pathfinding domains straight line distance (SLD) is suitable, since it is easy to compute in Euclidean spaces and is guaranteed to never overestimate the cost in monotonic cost domains.

However, in non-monotonic domains - for example, where an agent can use portals to move between locales - A* fails without explicit remapping of the domain to a monotonic cost space. This is not a trivial exercise.

If the heuristic is easy to compute and we know that the cost function is monotonic on the search domain, then discretising either the action space or state space and using A* is the better way to go, since we know it will expand less nodes than any other search algorithm.

The real benefit I have seen in using the DTA is in 3D pathfinding, where an oct-tree representation of the domain was used for finding paths. This makes performing the fill and hill climb exceptionally efficient, especially if more than one search is to be performed. In some games this representation of the domain could come directly from the graphics engine, so there is no need to ''double up'' in the building of this data structure. I haven''t actually seen this done in a game though... the implementation was for a 3D mobile robot (helicopter) moving in an obstructed domain.

quote: Original post by Geta
Also, do you have a good argument for why such a comparison might be useful to game developers?

If you can show that there exist a sufficient number of game domains in which A* is not suitable (for the reasons I have given above), or where the use of associate data structures (that are already computed in the game) would make the DTA more efficient (due to less computation), then you would certainly have a case for evaluating just how close these methods were (and preferring one over the other in said domains).

Ultimately, I''ve been pushing the DTA a little more than A* lately because it is exceptionally easy to implement and understand, especially for those people who are just beginning in pathfinding.

Cheers,

Tim

TerranFury: Thanks, those were the advantages I thought of too. Its good that others had the same opinion.

Timkin: Thanks. I''ve made my case to the section editor (based on my own assessment supported by TF''s and your comments), and if the article is accepted, then there will be an article in the next edition of Game Programming Gems that demonstrates the DTA in several path finding situations and compares it (performance wise) with an A*. Of course, the section editor may not select this article to be included.

In that case, I may write it anyway, and see if gamasutra or AI Wisdom or Game Developer want to publish it.

Any additional thoughts you have on DTA''s use in games, or references you have where DTA has actually been used in path finding would be appreciated.

Thanks,

Eric

Thank you guys for the great discussion on this post. Even though I have not posted any comments, your dialog has helped me out alot. It''s these kind of threads that keep me coming back.

Code-Junkie

quote: Original post by Geta
Any additional thoughts you have on DTA''s use in games, or references you have where DTA has actually been used in path finding would be appreciated.

I didn''t get home until very late last night so I didn''t have an opportunity to go through my rather large paper archive. I know i have a couple of papers that are appropriate... I''ll dig them out on the weekend.

Timkin

Okay, it appears that I have (for some very stupid reason) deleted my electronic copy of my archive??? I still have hard copies of most of the papers in my collection... I''ll dig them out and then work out where to post some copies!

Timkin

quote: Original post by TerranFury
Although the combination of floodfill and hillclimber is slower than A*, the hillclimber alone should easily beat A*. Therefore DTA would be preferable in this situation:
- The goal location is relatively static

Based on that, here''s one application relevant to real-world games:

1) Drag a selection box over 100 RTS units
2) Click on a destination or target

The benefit here is that you get 100 paths created almost in parallel (steering/avoidance issues aside). I doubt even the most optimised A* could beat this algorithm in this sort of situation. The initial floodfill might take a while though, maybe requiring a tiny bit of threading (and perhaps a separate data structure per player).

You see the same sort of thing in RPGs like Baldur''s Gate where you''re often sending 5 or 6 people to essentially the same place.

[ MSVC Fixes | STL Docs | SDL | Game AI | Sockets | C++ Faq Lite | Boost
Asking Questions | Organising code files | My stuff | Tiny XML | STLPort]