Pathfinding

[eaterofspleens]

Sorry, I'm a great fan of Exult, and of the astounding acomplishment of this project over the years - but there is one thing that really does let it down. The pathfinding is atrocious! I was playing Serpent Isle a moment ago and ran into some goblins. Two of my party decided to very slowly chase a goblin who had decided to wander randomly to the right for ten miniutes. Another stood completely confounded (Dupre of course) as to how to find his way around a tree. This left me to take of the other six goblins by myself. Great.
I know how hard it is to produce good pathfinding algorithms, but as things stand (or wander randomly to the right depending as far as I can tell on the phase of the moon), it is pretty much the only area where Exult is still lagging behind the originals.
Oh, and I've noticed pikemen dissapearing inexplicably from Monitor. Odd.

[Michele]

I would not blame Exult for that, I had the same prob Playing Serpent Isle when it was first released.

Should be provable by playing Serpent Isle (or Ultima 7) in DOS Box.

[DreamMaster]

As for the pikeman disappearing, there may be someone else who's discovered just how much money they can make by killing them and taking their carcasses to the crematorium.

DreamMaster.

[drcode]

I think a lot of those Pikemen are egg-spawned 'monsters', and they get tossed away if you walk more than a screenfull away.

[eaterofspleens]

Sorry if I came across as a bit negative there - I was in a bad mood for a variaty of reasons, being repeatedly slaughtered by goblins being only a minor one.
I remember the pathfinding in the originals being better (although my memory may be blurred by time and drink and wishful thinking), I particually don't remember enemies wandering past you to attack the spot you were twenty seconds ago habitually for example.
As for the pikemen thing. Its strange. One of the pikemen who mans the north gate has dissapeared, as well as unfortunately the one who lets you train at the list field. They're gone permenantly as far as I can see...

[wjp]

http://exult.info/faq.php#pikeman_disappears

[eaterofspleens]

Crap - and I have actually read the faq. It was a while ago, and I missed / forgot that. Thanks.

[Dominus]

I particually don't remember enemies wandering past you to attack the spot you were twenty seconds ago habitually for example.

This is caused by eggs that trigger monsters to spawn. It may be that Exult triggers them faster but if they are meant to be retriggered the behavior should be the same in Exult and the original.

As for the FAQ, it is a work that is never finished. At the time you read it, the entry might not have been written yet.

[eaterofspleens]

But the pathfinding algorithm is not the same as in the originals I'd guess? It seems like the pathfinding chooses to walk to where its target is, then once it gets there looks again - by which time the target is half way across the screen. This leads to enemies running past you as you both meet, and you spend time running after an enemy who should be attacking you but seems intent on sniffing your droppings from five miniutes earlier.
Like I said, I'm well aware of how difficult an issue pathfinding is (took an AI course at uni briefly before giving up in bewilderment), and the implementation you have now is reasonable, it just seems to be one of the few things in Exult that could stand to be improved...

[Dominus]

Of course the algorithm is not the same How could it be since no one has the source anymore?
But all you are describing sums up the issues I encountered when I played U7 ages ago. Only with Exult the issues seem to be more apparent since the party moves way faster than the crawl back then
Tweaking the pathfinding is not that easy I think, since the more accurate you are, the more CPU power is needed and the slower the gameplay gets. Ages ago in Exult, monsters were too persistent in trying to find a path and slowed the game down noticeably.

[drcode]

Bob: You've described the problem pretty accurately. An NPC will call the pathfinder to get to an opponent, then walk there. If the opponent has moved, it looks pretty silly. There's code to have them check when they're part-way there. The hard part is determining where 'part-way' should be. If it's too often, the pathfinder (which, as Dominik pointed out, is very CPU intensive), gets called too much and the game slows down.

[wjp]

Maybe we should add some extra logic to that 'part-way' code. Maybe store the direction and distance the opponent is in when starting, and when that angle changes too much or the distance is far less than it should be, pathfind again. That should at least take care of the case where monsters walk right past you. Of course that would also trigger re-pathfinding when the monster has to walk around a big obstacle, but that shouldn't be too much of a problem, I hope.

Another option is calling a very basic pathfinder more often, possibly even a strictly line-of-sight pathfinder.

[drcode]

Looking at "Approach_actor_action::handle_event" in actions.cc, it looks like we're trying to do something like that. When an NPC is about half-way to his goal, he sees if the opponent has moved. If it's more than two tiles, he quits his current walk, and (supposedly) tries again for the new position.

Maybe we get situations where two NPC's are approaching each other along different paths, because there's an obstacle inbetween, so they appear to be wandering aimlessly.

[Debonaire Hero]

I remember in Baldur's Gate they had an option where you could set the amount of nodes used in pathfinding, so computers with the extra processing power could get better paths. I know that's not the same variable you're talking about tweaking here, but maybe it would possible to include an option that determines how often the paths get redrawn?

I've written an A* pathfinder for my game, and it doesn't seem like this would be too hard to implement there.

[Michele]

Modding BG and modding Exult are a bit different.
I used to work with the peeps at TeamBG doing some scripting.

[Alun Bestor]

I seem to remember the pathfinding in Baldur's Gate going beyond atrocious and into the realms of farcical Even if you ramped up the number of nodes to unplayably high, you'd still end up with half the party taking The Long Way Round to get to a monster just because another party member happened to be blocking the way a second too long. Which isn't a problem for Exult of course, since NPCs are non-blocking.

[eaterofspleens]

Baldurs Gates pathfinding certainly did have comedy value. "Oh dear, I can't get through that door as someones standing in it for a second, so I'll go round, via switzerland.". Being able to choose how oftern the pathfinding updates isn't a bad idea though.
I don't really have anything to add for a possible solution I'm afraid, and I feel a bit mean for bringing it up in the first place. Possible have actors just take a direct line towards their target, and then only call the search tree when they hit an obstacle? I dunno...

[drcode]

I might take another look at Exult's pathfinding this week. The hard part is testing; ie, getting a scenario that's the same each time. Otherwise it's difficult to tell if a coding change improves anything, or makes it worse.