[General algorithms] Pathing

[King Harold]

What would be the best way to deal with pathing in a tile-based landscape in which some tiles are 'illegal' to walk on (water.. mountains.. buildings..)?
I allready tried a very simple thing which i made up myself during math class (when else? ) but it has a very nasty problem..
When there's only 1 obstacle (no matter what the size) it works quite good.

It will reject the purple line (the lower one) because its longer (yes it tries every possible way and keeps the shortest)
However, when you put in more obtsacles, say 2, it will sometimes find reason to "keep going round", it will think it can choose to go back because its therotically possible its the shortest way, and then reach that same point again at which it can choose again, the biggest problem is that the calculation of the other ways will pile up because everytime it chooses it also has to calculate the other way. (the other 2 purple ways are rejected because they are too long, in fact the upper one wont even be tried)

That's easy enough to solve by keeping track of where it has allready been and give up when it hits itself again (kinda like playing snake ).
(sounds like A* I know, but I can assure you I didn't even know it existed when I thought of this)

But I am aware that this is neither the best nor the fastest way for pathing, so what do you all suggest?

[CoBB]

The standard algorithm for this kind of pathfinding is the A* algorithm.

[threefingeredguy]

Doing queues in BASIC will require a lot of list manipulation.

[King Harold]

Sure would, but Im not too bad at it, unfortunately it isn't just BASIC.. Well, unfortunately, it will be lots faster then BASIC, but that doesn't mean it will be any easier.
I've heard of good mathimatical pathing algorithms, not just trying like A* (or the buggy version I invented during math class), also heard something about voronoi diagrams being used.. but I can't find something that makes sence..

[Dwedit]

A* is just a bredth first search which favors choosing shorter distance points.

[King Harold]

Yes that's the problem, although it's simple and works, it isn't at all fast, and I know there are better ways then A*.
But Im having bad luck finding them with google, so I hoped someone here would know some alternative pathing methods..

[kalan_vod]

Have you looked through Wiki?

[King Harold]

Can't say I have, worth a try..


But now I have and it only gave A* and dijkstra's thing (that's a dutch name, dijkstra), which is really a lot like A*.
But I'm really 100% sure that A* is neither the fastest, nor the only pathing algorithm.
Forexample I've heard something about voronoi diagrams being used, and there should be other methods aswell. (nice mathimatical algorithms that will calculate the shortest way rather then calculating the difference between the distance between the point where you are and the point you are trying to go to and the difference between any point around you that you could go and the point you are trying to get to.)

[coelurus]

A* is a general pathfinding algorithm that will always give you (one of) the shortest path(-s). Without any sort of information about the "pathing environment", there is no way to make an algo as robust and safe (there have been a couple of these threads here before ).

[kalan_vod]

I would trust coelurus on this one, he knows what he is doing . Thanks for the information guys, even though I am not currently working on a program which requires a path finding algorithm, I will put it to use.

[kv83]

A* is indeed the most common and propably the best pathfinding there is.

[coelurus]

"Probably" with respect to the problem. Referring to my last post, A* is a general solution and it can be way too ambitious if you got some restrictions on the path.

All right, that wasn't necessary, but I don't wanna pick up my S.P. "homework" just yet :p

[King Harold]

So.. what you're saying is "just use A*", right?
You know, that's fine by me really, but I'm still wondering what the alternatives are (and Dijkstra's algorithm is so similar to A* that I wouldn't call it an alternative)

But A* can't be the best, its basically "just trying" (ok its only trying the right direction, but still) so anything mathimatical should beat it, even if it's complicated it should only need to calculate something once instead of having to calculate the way for all nodes that make sense..

prove me wrong

[CoBB]

What do you mean by ‘mathematical’? Optimisation (of which pathfinding is really just a branch of) is an area where you can hardly come up with any kind of guarantee, let alone closed formulae. You need to be creative, because there are no general methods (‘metaheuristics’ in fancy-lingo) that would excel at every possible task. The right thing to do is going on a googlefest and finding out what methods people usually use for similar problems and with what results, gathering ideas from those and then starting experiments to create the method that’s ideal for your own task. There are no other shortcuts here. If you want good results, you can’t avoid the personal struggle that leads to them.

[King Harold]

A* is so widely used that I can't get anything else outof google.
So yes well, I guess I'll have to go through the "personal struggle"..
Or I could just settle for A*, atleast for the time being, and worry about it later. (which is probebly what I am going to do, I don't really like the idea of a 'personal struggle' )