Multithreading

[Andrea B Previtera]

Someone, someday, was going to open *this* particolar thread. Let me take care of that

Without even touching the subject of multicore cpus and such, I was thinking that, for example, the pathfinding would benefit a lot by being put into a separate thread. Right now - for the little I played with the code - it seems to be one of the things that make the game hiccup now and then.

Engine doing stuff -> Wait for NPCS, Monsters etc. to pathfind -> Go on and finally render

Would become

Engine doing stuff -> Go on and finally render
and concurrently:
NPCS, Monsters are pathfinding. When done, move them

[I am making this obvious for non-coders of course, not for the Exult team ]

So I am wondering: how much is the pathfinder entangled with the rest of the engine? Does it produce data that is fundamental to the execution of the main thread, every frame?

[TdI]

I can't answer your questions about multithreading, but let me add (perhaps agree) that the pathfinding and moving of NPCs is IMHO one of Exult`s weak spots.
Compared to the original, NPCs move to slow, to hesitatingly and often head for a place that was the correct target 5 seconds ago. To understand what I mean, just compare the way the major follows you around in Exult to how he follows you around in the original. When the Avatar is moving, the major continues to walk in the wrong direction for a while after noticing the new Avatar position.

[Colourless]

There is really two ways of multithreading pathfinding. One is a bit easier than than the other.

You could just do normal pathfinding but using more than one thread to calculate it. If doing A* you would have more than one thread popping off nodes to check at a time. Implementing this in the context of Exult wouldn't be too hard, but would have a really small actual benefit in general use, but should provide a good speed increase in worse case scenarios i.e. failure to find a path.

The other method would be doing complete async pathfinding. You have a couple of different options here. The easiest would be create a new thread to do the pathfinding, and then when the NPC needs to move, do a join to ensure the path has finished being calculated. This isn't too hard, but will have problem with needing locks on the world if things move, but that is exactly one of the problems currently in Exult as is. If the target moves, or if something blocks the pathfinding NPC then the path isn't recalculated right away. There are ways to fix this such as if an object moves or is created in a chunk then check against all currently active paths and recheck the path if needed.

Of course Exult dosen't recalculate paths very often because they are so 'expensive'. I don't really know why are they so expensive. We're obviously doing something a quite wrong as the original on a 386 has better performing pathfinding that we do on machines that are hundreds of times faster. A* itself isn't that expensive, especially not for a rigid tile based environment like Exult, but there is probably something in the details of how Exult is implementing it which is why we've got problems. Fixing the pathfinders general performance problems would do more to help than multithreading it. Perhaps running it through a profiler would help.

-Colourless Dragon

[Andrea B Previtera]

I can tell you that I implemented A* exactly as it's meant to be, I am making it work on a fixed tile environment, and darn - it IS expensive. I can't imagine multiple issues of it running smoothly on a 80386 machine. Also, as expensive as it is in general - it is practically blocking when it fails.

That's, mostly, why I thought of it as the main thing to disentangle and throw in a separate thread in the Exult engine. Also... I can't actually see anything else that could be ran concurrently. Egg processing?

[artaxerxes]

it's too bad the source code for U7 is lost. It would have been awesome to see how they did their tricks for optimization. The Zaurus could really benefit from u7's original engine designs.

Artaxerxes

[TdI]

I can imagine that the original doesn't use anything as sophisticated as A* for pathfinding. Maybe it doesn't do any pathfinding at all and the code is as simple as moving one step in the direction of the target. If something is in the way, the moving NPC takes a step in a direction that isn't blocked until it can move in the desired direction again.

I think something like this would be pretty effective in the case of U7, where the paths are usually very short and obstructed only by a few objects or linear walls.

This method, plus a few "emergency" functions, like the one that beams NPCs near where they want to go if they can't keep up normaly (in case of companions following the Avatar) may be close to how the original works.

[wintermute_turing_ai]

Correct me if I'm wrong, but there are so many pathfinding algorithms already available anyway, right? I would find it hard to imagine that the U7 team had anything better than what we have now.

[Skutarth]

If I had a time machine, I would go back in time and warn Richard Garriott to make sure he kept the source code safe. That would sure make the Exult team's job easier.
Also, to keep the near-gold copy of Lost Vale safe to eventually release. Who knows, though. That one may still exist somewhere.

[Dominus]

That would sure make the Exult team's job easier.

It most likely would have made our job easier years ago. At the stage Exult is now at, it sure wouldn't help THAT much anyway. Sure you could look things up but the way things got implemented must be so different now that you couldn't just take the original code (not that you could do that anyway... copyright...) and make it fit. IMHO

[Andrea B Previtera]

Tdi:

> I can imagine that the original doesn't use anything as sophisticated as
> A* for pathfinding.
> Maybe it doesn't do any pathfinding at all and the code is as simple as
> moving one step in the direction of the target. If something is in the
> way, the moving NPC takes a step in a direction that isn't blocked until it
> can move in the desired direction again.

Ah, I thought it was that simple too before I began coding my game Unfortunately, it is not, it's an approach that simply doesn't work at all and it takes ages to understand why - until you don't try implementing it, and you understand that in a matter of minutes.

U7 did use A* indeed, only I am sure it implemented a number of dirty tricks. My theory is that they had some precalculated stuff or something like that (Doom monsters use a similar approach), otherwise it's pretty unexplainable how could they run that on 80386 class machines.

[artaxerxes]

well, the only way I could think would be to have some assembler guru making sense of the binary. Since it was running on Dos (and thus, tell me if I'm wrong, single-threaded) it should be a tad easier. Not that understanding assembler is easy!

Then of course, you get all the issues of clean-room design.

Artaxerxes

[Andrea B Previtera]

Although there was sort of a multi-threading, it was all about concurrent applications - and applications were single-threaded. Actually given the way A* works - an assembler rewrite wouldn't help that much, trust me (I did a LOT of assembler back in the Dos days )

I will conduct some A* multithread experiments and tell you what happens. I am sure I can get some result..

[drcode]

I think Tdl is correct. When U7 was written (around 1990-92?), A* wasn't well-known, and probably would have been too expensive on a 386. The original U7's pathfinding wasn't particularly sophisticated, but it was fast and efficient. I'm pretty sure you could evade monsters by hiding behind things. It might be fun to run the original with 'hack-moving' and experiment with various shaped obstacles.

Exult's problems (which I think aren't that bad in the recent snapshots) don't exist because the pathfinder is too slow, but that it's called inappropriately. Sometimes we've called it too often, which slows the game down. Other times, such as for a monster during combat, it's too infrequent, so the monster stays on its original path long after you've moved out of the way.

We could also do better handling cases where an NPC is following a path, and the path gets blocked. Currently, we delay a second or two and then compute a new path, when it would be more efficient to try to get the NPC to step around the obstacle.

[ced]

maybe useful --> http://www.geocities.com/andre_leiradella/#apf

[ced]

and this --> http://www.blitzcoder.com/cgi-bin/showc ... omments=no

[ced]

last one, really good tutorial --> http://theory.stanford.edu/~amitp/GameP ... cs.html#S2

[Andrea B Previtera]

I've tested the original under dosbox constructing a large maze of walls (1.5 x 2 screens). A headless (he can't even actually see the party! ) managed to follow me from the middle of the maze to the exit to attack me. It's definitely A* in my opinion..

[Dominus]

Sorry folks, by request I cleaned up this thread a bit. As far as the public is concerned the origina code is lost. The only "person" who can claim to have the original source code is EA (since Origin ceased to exist). Anyone else is not allowed to have it or even more so, to give it away. Please don't pester anyone about it. Thanks.