Path Finding

[sesobebo]

fresh from replaying ps:t

 

i know it's about a millennium old (give or take a few centuries).

i have no doubt that p:e will have it better.

but this can't be stressed enough:

 

real time games (even with pause) need good path finding.

 

that is all.

[TheRealDrMcCoy]

Yeah, pathfinding is a common thing that never quite worked corrently in Infinity and Aurora (and following) engine games.

Be it companions that bumped against each other while walking in a line and backtracked around the whole room, or characters not moving through doorways while in combat mode, pathfinding always needed manual attention everywhere.

[mstark]

I agree wholeheartedly, as I'm just replaying BG2 myself. I think there's no way of getting away completely from at least some manual manipulation in a games like IE/PE, it's just the nature of the game, but the devs have said that they will work on good pathfinding algorithms (I think it was said by Adam).

[rjshae]

Yes I really, really hope they can fix path finding and make the path following algorithms look a little more plausible. I.e. more like following a cubic B-spline than a segmented line. I know it's a complicated problem when you include collision avoidance, but it would be very nice if they can pull it off.

Edited November 5, 2012 by rjshae

[Jajo]

Oh, yes.

I'm playing ToEE and I've been very surprised at how much the awful pathfinding is ruining the game for me. I unintentinally allow myself to be vexed by it to a point of resignation or quitting. But what can one do, when clicking one screen away often results in only 40% of the party finding it's way there.

[Malkaven]

fresh from replaying ps:t

 

i know it's about a millennium old (give or take a few centuries).

i have no doubt that p:e will have it better.

but this can't be stressed enough:

 

real time games (even with pause) need good path finding.

 

that is all.

 

Replaying BG1 and taking a whole lot of coffee breaks when a party member decides to thake the long way. They also love to stand on the loot too, ARGH!

Edited November 6, 2012 by Malkaven

[steelshark]

Just playing BG:T, and what really bothers me is that the party does not move as a cohesive unit, but rather as 6 individuals, that also sometimes block each other.

 

They should try to keep formation even while moving (no jumpstarts from 1-2 characters).

Perhaps in addition to formations characters could get tags such as "front, center and rear" for the game to know which characters should go first through doors/ tight halls.

ie.:

6 people, 3 tanks

I want 1 tank as a rear-guard.

So i tag 2 tanks front, 3 normal as center, and 1 tank as rear.

[Carmelle]

In this area, I would love if the game took a bit out of some recent RTS games that allow for formations... where you can have individual movement per character but as they move, have them try to adhere to a single formation too.

[Tamerlane]

In this area, I would love if the game took a bit out of some recent RTS games that allow for formations... where you can have individual movement per character but as they move, have them try to adhere to a single formation too.

Recent? Hell, Age of Empires 2 is over a decade old.

[Carmelle]

In this area, I would love if the game took a bit out of some recent RTS games that allow for formations... where you can have individual movement per character but as they move, have them try to adhere to a single formation too.

Recent? Hell, Age of Empires 2 is over a decade old.

Lol, true enough. In my mind I was thinking more along the lines of the newer Total War games as the basis. But yea, even the older TW games and AoE2 and such had pretty decent pathing with formations.

[Starglider]

They should try to keep formation even while moving (no jumpstarts from 1-2 characters).

 

This is the most important point in this thread. Simple pathfinding failures are easily solved by brute force : modern CPUs can do path refreshes much more frequently and effectively have no path length limit. Making the party move realisically requires algorithmic changes; using actual motion control / formation logic and treating character motion as a joint optimisation problem, instead of just individual A* on each character.

[teknoman2]

path finding with "You must gather your party" was a real pain in IE games, and pathfinding is still an issue in NWN2, where often some characters just stay back if they are in puppet mode and dont auto-follow the leader.

[Jajo]

They should try to keep formation even while moving (no jumpstarts from 1-2 characters).

 

This is the most important point in this thread. Simple pathfinding failures are easily solved by brute force : modern CPUs can do path refreshes much more frequently and effectively have no path length limit. Making the party move realisically requires algorithmic changes; using actual motion control / formation logic and treating character motion as a joint optimisation problem, instead of just individual A* on each character.

 

I would have thought, that characters actually finding the path would have unquestionably been more important.

I would also deem algorithms not taking a few seconds to determine the path to be more important than characters stepping out of the line. But that really is a personal preference from playing some of the old isometric RPGs in the last couple of months.

Also, do not think, that old problems will go away by themselves just from brute forcing with younger CPUs. If you do, try to play some of the old games on a contemporary machine. Yes, they can increase the number of search nodes, but what's the point, if it takes a few seconds for the path to be calculated even now? Algorithmic changes are indeed in order, but they should not be done just (or mainly) to support formations.

[Starglider]

I would have thought, that characters actually finding the path would have unquestionably been more important.

 

Sure but that's trivial on modern CPUs. The old IE games only had single-path problems due to lack of adequate CPU power.

 

I would also deem algorithms not taking a few seconds to determine the path to be more important than characters stepping out of the line.

 

The problem that doesn't go away even with infinite CPU power is trying to fit multiple characters through a small gap. Naive single-entity pathing algorithms just do not handle this well even with hacks to try and fudge it. Most modern pathing problems are caused by characters blocking each other and screwing up the pathing, not due to inability to path through the static environment.

 

Also, do not think, that old problems will go away by themselves just from brute forcing with younger CPUs. If you do, try to play some of the old games on a contemporary machine. Yes, they can increase the number of search nodes, but what's the point, if it takes a few seconds for the path to be calculated even now?

 

I don't have this problem but then I play on watercooled overclocked bleeding edge machines. Note that the old engines were single threaded, whereas a new engine should use easily use four or more cores for game logic calculations.

[Hormalakh]

They should implement some sort of "wait for a few seconds to see if choke clears up then push person out of way" implementation for pathfinding. It's what most people do in RL. You wait for the person to pass then follow along behind them, or you tell them to move out the way and go along your merry way. I think that pathfinding and a few other things should be player tested as soon as possible before the game comes out.

Edited November 14, 2012 by Hormalakh

[GhostofAnakin]

Yeah, pathfinding is a common thing that never quite worked corrently in Infinity and Aurora (and following) engine games.

Be it companions that bumped against each other while walking in a line and backtracked around the whole room, or characters not moving through doorways while in combat mode, pathfinding always needed manual attention everywhere.

 

Haha the bolded part annoyed me to no end, especially in areas that I hadn't explored yet and thus enemies would trigger "off screen" surrounding that one character while the rest of my party was on a different part of the map.

 

I probably should have been paying closer attention, but I shouldn't have to be too concerned when I click on my party to go through a door ten feet away and have to worry about one of them bumping into another, and deciding to take the long route to that room right in front of them.