Coders' corner #1004

[Andrea B Previtera]

On pathfinding, again. Exult uses A* - of course, but how did you implement the search of *best* path? All the implementation of A* I found (including the one I am using) focus on speed alone, thusly choosing the first possible path, not the best one.

[Colourless]

When using A* you wont always get the best path possible. The reason you use A* is to get a reasonably good path, fairly quickly, that will always manage to get to the destination if it's possible.

There are other algorithms that will get you the best path possible, but they are much slower than A*.

-Colourless Dragon

[Andrea B Previtera]

Right. The problem is that this path, occasionally isn't the shortest at all. Expecially when entering buildings from the wall opposite to the one with a door or another kind of opening. The path will trace the perimeter of the building, find the open area, and then
sometimes go straight to the point of the inside area you clicked
sometimes keep tracing the walls from the inside, until it's very near to that point, and change route.

I think this is all due to the arbitrary order in which you check the lowest cost steps. Two steps with the same cost may result in two completely different paths - but the clockwise one will always be the chosen one.

Anyway: another question. When the avatar is moved by keyboard, obviously you don't pathfind. You just move it of some units. But how do you check whether he collides or not with an object? This seems to suggest that you also keep a list of all the "collision zones". I also noticed that once you move him againist a small solid object, he will "slide" the number of pixels needed to avoid it. Am I right?

One more question: is your pathfinding completely dynamic? I mean: to speed up things, instead of keeping a list of the blocked points, I have a whole array representing the visible screen, subdivided into X*Y boolean values, which I set accordingly to the objects on screen each time it's needed. (To clear up things, imagine a B/W representation of the screen, black is passable, white is not).

That's all
Forgive me, I know you may just answer "exult is opensource, go on and read", but I have a really bad relationship with C. I can understand it, of course, but later I'll need some extra strenght tylenol!

[Colourless]

A* becomes more accurate the more accurate your estimation to the goal is. From the sounds of things, there might be something slightly wrong with your implementation as A* should not wall hug like you've described.

Exult handles colision detection by storing a bit for every (3d) tile in the entire world. This requires a few MB to store all the data. For any engine that is not tile based, this method will not work as the amount of data will quickly head into the GB range.

When moving the Avatar pathfinding isn't used. What we have is a function that can be called that can determine if an object can move to a new location. So basically we check to see if the Avatar can step forward.

If the step is blocked, then we check to see if he can step around the obstruction.

Also I wouldn't recommend you read how exult does things. There are much better examples out there.

[drcode]

You might check your cost-estimation function. It should depend on the true distance (sum of squares of deltax, deltay) between two points.

[Andrea B Previtera]

Did that. Real distance, all calculus done in floating point, too (I don't think it counts, but...)

I am REALLY interested in that "bit-map" of the world passable/unpassable zone... right now I "draw" this map in realtime each time it's needed (well, also because some solid objects are movable anyway. Think of chairs).

[Andrea B Previtera]

Further explanations with visual aid.


Normal






Wrong






Very wrong

[Colourless]

Just being sure, where is the start of each path? Is it where the person is, or is it the other end.

Regardless, your algorithm is just plain broken. It is hard/impossible to say what exactly is wrong without actually seeing it.

Now, from looking at your collision boundries, using a bitmap for CD probably isn't a good idea. When doing CD you do bounding box tests rather than doing 'is blocked' checks into your bitmap. You should probably be storing your world into 'chunks' of some sort (if you aren't already) so you can quickly access a small number of items in an area. This allows you to easily cull objects that you know wont be colliding.

-Colourless Dragon

[Andrea B Previtera]

The person is on the *end* of the path. Yes: something is obviously broken. Still it works: it's this that puzzles me. Despite wrong, it will perfectly work for the worst cases (I set up a very complex labyrinth and it always find the only possible way through it, quickly too)

As for the bitmap - no no, the bitmap is just used for A*
For collision detection I'll just use polygon to polygon tests. Should be fast, since the world is tile based and I'll just have to check a polygon againist the other polygons linked to the same tile.

[drcode]

I've been throught the same sort of problems. You want to get into your debugger and start stepping through the algorithm right after the path has entered the building. The cost to take a step directly towards the goal (single-step-cost + estimate based on distance) should be less than a step around the perimeter. Since the single-step-costs should be the same, it's only the estimate that's going to vary. Are you sure you're using the correct points?

Also, just for a bit of efficiency: You don't need to use floating-point for the distance, because you don't need to take the square root.

[Andrea B Previtera]

You may notice that something weird happens even before entering the building: the path goes zig-zag now and then, while it should just go straight.

What do you mean by "the correct points"? I don't know but I feel this might be the key... keep in mind that I developed my a* pathfinding from a simple step to step description in english... and - miracle! - it worked

As for floating point: right! Thanks, I didn't think to that

[drcode]

The zigzagging can happen if the step cost going diagonally is the same as going horizontally or vertically.

By 'correct points', I mean: Are you running your estimate function on the point that you're considering stepping to, rather than the point you're currently on?

[Andrea B Previtera]

The diagonal cost is ok, I add a cost of 10 for straight steps and 14 for diagonal steps.
As for running the estimate function... uhm, I think you may havee found the problem! I will check that asap, thanks.

[drcode]

Okay, you're doing the step cost correctly. When I first worked on Exult's, I made the diagonal cost the same as the horizontal and vertical cost. This resulted in the following paths from A to B:-)


A B
X X
X X
X

[drcode]

Hmmm, that didn't come out the way I typed it. Well, think of an arc between A and B, instead of a straight line.

[Wizardry Dragon]

I think what you're looking here is for a more "natural" seeming pathfinding alogrithm. What I often end up doing is have the algorithm make natural (curved) turns (instead of artificial 90 degree turns) and make sure that your always x distance away from scenery. Those seem to be the two points to implement that make the biggest difference in making a "natural" seeming pathfinder. The challenge is to do both efficiently, and there I have to conceed that I have not yet got that down.

~ Wizardry Dragon

[Andrea B Previtera]

Wizardry: no, actually I just calculate the path as it is, with the occasional
90° turns - I smooth it afterwards, while moving the objects according to the path. During this phase I try to smooth those hard angles with some tangent linear interpolation, provided that there are no obstacles (if the hard turn is due to a wall, I can't do anything)


DrCode: I am on the... path to the solution. You were right, the estimate cost was added in the wrong places. But other flaws still exist. Thanks!