Exult Forum

I downloaded the source code for Exult, nonetheless I must admit that
I quite suck at retroengineering, even when projects are opensource : )
C code makes my eyes bleed, it's my limit! (infact I still keep coding
mostly in assembler+pascal).

Well, I've got this pathfinding problem, which is quite easily explained
in the two images I link here:

http://www.lalista.org/1.gif

http://www.lalista.org/2.gif

I must go from point A (xa,ya) to point B (xb,yb).
I find the points in between with linear interpolation, as
shown in figure 1

BUT there are collision zones I must avoid. I've got a list of those
zones, in the form of X1,Y1,X2,Y2 coordinates. How do I modify
my route to (see figure 2) avoid the zones? I can find some solutions
by myself, but none seems to be efficient and/or elegant.

And, most importantly: how do I "understand" that a certain
destination is actually unreachable?

Finding the optimal path is actually fairly simple (if you are using a simple 2d grid). What you want to be knowing about is the A-Star (or A*) algorithm.

While I wont get into the exact details of how it works, I'll give you some details. Quite simply, the algorithm continuely takes steps towards the destination from the source. The algorithm will only take a single step at a time and will check to see if the next step is blocked. If the next step is into a blocked area, it attempt to step into the next best spot. The algorithm also remembers when it's already been to a certain spot, so it wont go back to that spot. For instance, if it takes a step to a place is completely surrounded, it will not step back to where it came from. Instead, it will restart finding the path from the previous stop. How this all works though, is best explained by someone else. You should read articles on pathfinding at places such as http://www.gamedev.net/.

Working out if a destination is unreachable is not a simple problem. While the most obvious way would be to check every tile in the world untill all of them has been checked, this is extremely slow. Usually, the way to do it is to have some cut off point after the path has reached a certain number of steps. If it gets too large, then you say it's unreachable. This can be unreliable though

how about going the OTHER way around? finding a path from the DESTINATION to the starting point. that way it will be quite easier to determine if the destination is unreachable. (but what if the starting point is surrounded?)

The problem is completely symmetrical. It doesn't matter if you begin at the start or at the finish.

(Starting at both sides at the same time may be interesting, but that's another thing )

To add another point about symmetry: Sometimes you want someone to reach a certain square on the screen, starting from anywhere offscreen. In that case, it's easier to use the end-point as your source, and consider any point off the screen as a successful destination.

Well I thank you all. I managed to find a quite intriguing solution. Only
a flaw remains in this pathfinding algorythm I am developing, but I will
correct it as soon as I can find a nice method to understand from
where the intersection between the straight path and the collision
zone comes. (North, East, South, West)

Don't worry if your algorithm seems sub-optimal. or doesn't seem to work
efficiently in every circumstance. Imagine the most extreme situation -
pathfinding in a labyrinth. Then finding the shortest route from one place
to another place, or even determining whether one exists, is what's
called an NP-complete problem. Roughly, this means a problem whose
solution can be checked quickly (in polynomial time), but which is at least
as hard as every other NP problem, which includes famously hard
problems, like e.g. the travelling salesman problem for which there is
no known fast algorithm, and conjecturally none exists. But maybe you
already know this from CS class.

Well, not from the CS class I never took (I am Italian and Live in Italy, there's no such stuff here) - but yes, I know the problem.

I think that for the P versus NP problem there's also a reward of
something like 1 million Euros, so...ahem...I fear I won't be the one to
solve it

The problem with for instance the Travelling Salesman problem is if you have managed to find the optimal route, you've then got to prove that no other route is better, and that quite possibly IS the real problem.

The TSP as a decision-problem is usually phrased as: "Is there a trip of length Then finding the shortest route from one place
> to another place, or even determining whether one exists, is what's
> called an NP-complete problem.

Determining if there's a path from one point to another in a graph can be done with breadth-/depth-first search. (O(n^2))

Finding the shortest path from one point to another can be done with Dijkstra (O(n^2)) or if there are negative path lengths with Bellman-Ford (O(n^3)).

So, both problems are P, not NPC.

Oops I mis-posted - I meant to say it was NP-hard. Wait before
flaming me wjp - I read your post, and I agree with it, but I
had something slightly different in mind:

It's true that finding the shortest path in a graph is polynomial in
the size of the graph, but in pathfinding the "size of the graph" is
(essentially) infinite: you might have to take a very large detour
to get to a point only "distance n" away. Even if you just want
to know whether there's a path of distance < n from where you
start to your goal, you need to potentially search your whole
diameter n neighborhood, which is a graph of size exponential in n,
for typical bounded valence graphs. I'm pretty sure that's an
NP-hard problem (I agree it's not NP-complete).

If your "graph" is a subset of the rectangular grid, then
the subset which is distance n away is only of quadratic
size; but even in Exult there are "neighborhoods" which are
not subsets of the rectangular grid: staircases, ladders, teleport
pads, etc.

Hm, yes, looking at it in that way the problem becomes slightly more complex

/me wonders how to proof it's in NP-hard.
A problem is in NP-hard if all NP problems can be polynomially reduced to it, right?

Hm, it might be even 'harder' than NP-hard. Given a random NP problem of size n, try to polynomially reduce it to an instance of this pathfinding problem. Since it's a polynomial reduction, the graph that's generated by this reduction has to be of size polynomial in n. (Unless maybe you represent the graph implicitly somehow? Ugh... Would depend on the the way you phrase the pathfinding problem, I guess)
But if the graph is of size polynomial in n, the pathfinding would take polynomial time too. That would mean either P = NP, or this pathfinding isn't in NP-hard.

Of course, it all depends on the exact phrasing of the problem in question, too.

Please correct me if I'm wrong; it's been a while since I really thought about P/NP/NP-hard/etc... complexity issues

One thing I just realized I missed: complexity is in the total input size, so that includes the full graph.

One thing I've discovered working on Exult: It's not so much the speed of your pathfinding algorithm, but how smart you are about calling it. There have been lots of problems with game slowdown because pathfinding would fail (because a monster was in a locked room), but then I'd try again on the next tick. With a few monsters around, the game would stall. But if I disabled pathfinding after a failure, you could unlock the door, and the monsters would ignore you.

Some more questions to the Exult coders:

ok, so I have this pathfinding algorythm. It works, more or less, except
for certain special cases which I can avoid. Yet, I realized something
horrible:

the pathfinding algorythm, this one as well as many other pathfinding
algorythms, check a single pair of coords x,y againist the collision zones.
Now, this is not my (our?) case! The player, monster, they all have a
collision zone of their own, a square that inscribes their feet or some other
zone of their body. This zone must be checked againist the other zones.
Or not?

Also: let's assume you've got this "leader" that is the character you move,
the character that's always in the middle of the screen. Now - I can
perform pathfinding for him - but what for the characters that are in
formation around him? To keep the formation, their "destination points"
could fall on some obstacle. I am puzzled.

Here's what Exult does: Pathfinding is done for each character separately. So the Avatar moves first, and then pathfinding, if necessary, is done for each of the companions to get him to keep up.

But we try to avoid pathfinding as much as possible. So if Iolo just needs to move two steps to the right, and those are clear, we don't need to call it.

Ok but I mean: what if those two steps, or whatever the final destination
of Iolo falls into an unwalkable zone? How do you determine the "nearest neighbour"?

In that case, you look for an occupied spot as close as possible that you can pathfind to. If you fail, you might have to leave him alone for a while, in hopes that the Avatar moves someplace where there's more room.

It DOES get tricky, and Exult certainly isn't perfect in this area.

The odd thing is, we have almost no idea how the original, on things like 20 MHz 386s managed to have pretty reasonable pathfinding, when it's actually been a bit of an issue for us on 1000 MHz P3s and Athlons.

Tricks. I am sure there is some kind of trick or pre-calculation of some sort, give the characteristics of the Ultima world.

By the way, my algorythm, simple as it is and completely unoptimized, isn't processor-consuming at all. The point is that, tracing a path in a tile-organized world means that for each step I can take care just of the zones that are linked to the tile where the step is being calculated.

Also, I don't work with costs and such, I just wrap my way around the square obstacles: I calculate *where* the intersection happens (North, East, South, West side of the square) and dependingly on this I can wrap my path around the area.

It's not always beautiful to watch... but it's damn fast. Think about it.

You should think about pathological cases. Most often problem is where a obstacle is large and wraps back behind starting location.

Example which can often cause problems for 'simple' algorithms. We want to go from the Red Square to the Blue Square. The Green blocks are the obstacles.

Also, the worst case is where the NPC has a lot of freedom of movement, but still can't get to the desired square. For example, if the destination is in a locked building, but the NPC is outside. We'll end up searching a looong way before giving up. (Maybe a bit of topology could help here...)

In such a case as DrCodes, a bidirectional search can help out.

You're considering the pathfinding on a "granular" plane, while I have a different approach. My collision zones are pair of coordinates: x1,y1,x2,y1. I have a list of those zones, so let's suppose that the thing you depicted is a house, and the single squares are walls.

I must reach that point inside the house. Well: my algorithm traces the shortest path, so it goes straight. Then, it meets a wall.It traces a new path that slides till the right (or left) end of the wall and then goes to the
point again.



But: ta-daa! There's another wall! So it goes sliding again. And so on.
The final result is something like this:



The yellow arrows are /attempts/ at going straight to the point, where instead the algorythm meets a collision zone and slides until the end of it. Then it tries to go straight to the point again. And so on. It's very, very, very fast.

But how does it act in reverse. In my example I wanted you to start the path at the red block and then go to the blue block.

I have a list of "covered points" so that you never return on a point where you've been before, thusly (I won't illustrate it this time... I just don't know how!):

We try the straight south path.
Wall!
We slide on to the far left wall.
At this point we trace the new path and that would lead south
again. but we can't go south, we can't slide right because the path
to "right" has already been marked, so the next counterclock choice
is going north, and north we go. And so on.

Just trying to ensure your algorithm is entirely robust.

Now, here I've illustrated where I believe there might be a problem with the path selection.

In this following image that illustrates the path, what will happen when the purple square is reached. Will it correctly choose the red path or will it choose the blue path. If it chooses the red path, why? If it chooses the blue path, will the algorithm get 'stuck' with no where to move. If the algorithm just wall hugs, under what criteria will it stop hugging the wall?

Gee, you were right, so now I added a little hack: the algorythm seeks for continuity among the collision zones. So once the path hits a wall, all the continuous (ie: overlapping or touching) collision zones are treated like a single entity. So, once I hit this "big zone", I can slide all over it's edges, thusly choosing (in your case) the red path. The algorythm stops hugging the wall when, casting a ray towards the final destination, this ray doesn't encounter any zone of the wall itself.

It has been failry easy to implement - and I am still testing the performance impact, but seems to be not perceivable when dealing with 10 to 100 "zones".

how is the performance when performing multiple pathfinding activities?

anyways, I dub Andrea's algorithm:blind man finding a sound.

Ahem?

Performance will be better in some cases, and worse in others. It all entirely depends on how the algorithm works, and the map it's trying to navigate

Well actually now that I have re-organized the world so that "fixed" objects' (trees, walls) collision zones are pre-linked, so that I almost never have to calculate a "macrozone" in realtime, performance is excellent. Even multiple pathfindings don't impact the game at all. I shall give you more detail, with some visual aid, later : )