It's all in your head, Part 19

[elexis]

All the toilets are on one wall but the Male/Female toilets, even when they are adjacent, don't share a common wall for the toilets.

At least that is the case in more buildings i can think of.

[Lord Ozymandias]

All I can say is: Eeeeeeeeeeeeeeeeeeeee!

I'm glad I'm about to finish school, because school would have to take a backseat to a game like this.

The other day I was standing around with some other engineering students and a few of our professors and we came to the conclusion that the difference between a good product and a great product is getting the little things right. I'm glad somebody out there still gets their hands dirty to get everything right.

Introversion: you guys are awesome!

[martin]

Okay, this may be a really, really stupid question, but googling A* related stuff does not really answer it: for several of the paths calculated (nearly all that I saw?), near the end of the path there is a little ``wiggle.'' What is that all about?

I re-watched the video after you pointed that out and it's true, they all seem to have a little wiggle at the end. Obviously this is some quirk with the fact that the pathfinding is based on a grid and not a more representative navigation mesh. I imagine that kind of thing can be solved by a somewhat smoothed path.

Also, and this may be really nit-picky (and may not even be right), but the bathrooms seem off to me.

The wonderful thing about a procedural engine, is that you can change the script for the way bathrooms are laid out, and suddenly every single building in the city is correct. The modding possibilities for subversion are incredible...

[elexis]

I point you to this (4MB pdf). Is an irregular path all that bad? True, it looks bad when you can see the actual path, but the actual movement looks better, more human. But yes a smoothed path would help that further.

[Ace Rimmer]

Also, and this may be really nit-picky (and may not even be right), but the bathrooms seem off to me.

The wonderful thing about a procedural engine, is that you can change the script for the way bathrooms are laid out, and suddenly every single building in the city is correct. The modding possibilities for subversion are incredible...

You mean like toilets in the lobby?

[martin]

That's part of what I was thinking about, simply smoothing an irregular path a little is more natural (and easier to program) than genuinely finding the shortest path. Sometimes a bug really is a feature

What about the toilets in the lobby. I can't be bothered to watch the video *again* :p

EDIT:: By the way, interesting read, thanks very much.

[xander]

That's part of what I was thinking about, simply smoothing an irregular path a little is more natural (and easier to program) than genuinely finding the shortest path. Sometimes a bug really is a feature ;)

What about the toilets in the lobby. I can't be bothered to watch the video *again* :p

EDIT:: By the way, interesting read, thanks very much.

I totally agree that a wiggly path may be more realistic, but my question is more about the quirk of the algorithm that causes it.

xander

[Chris]

Yep, that wiggle at the end is caused because your desired destination is in 2d space and could be something like "x: 24.9, y: 67.2", but then that gets rounded up to the centre of the nearest grid cell, so the final node ends up being "x: 24, y: 67".

You can tell the routes generated exist on a grid, because you can see the angles between parts of the generated route - like you say it doesn't look smooth. But in practice it doesn't matter - you'll notice when entities follow a route, they don't follow it exactly - they just head in approximately the right direction. So they're effectively smoothing out the generated route as they walk along it.

[martin]

So the entities do something like that valve paper described, approximately following an artificial looking path which results in a natural looking movement?

[elexis]

With regards to the hang you described when the computer is pathfinding, would it be better to not determine the entire path but to only determine the next part of it? It would mean that the person could start moving almost straight away and calculate the rest of the path while moving. (Or can this only be done with a nav mesh?)
This will also reduce the amount of wasted calculations if for some reason the person changed their destination while moving (quite possible for human controlled people)

[martin]

The problem with this is that the person can move down a dead end. obviously, in some cases, a character moving down a dead end can look more realistic...

[elexis]

What if it uses a larger grid for pathfinding further away from the person, and the small one it uses now for the immediate path. This means that where the person is walking at present is fairly optimal and accurate, and the later parts of the path that the person is not yet up to are inaccurate, but still correct and most importantly fast.

(Am I ignorantly talking rubbish?)

[bert_the_turtle]

The problem with the larger grid is that it still would need to be fine grained enough to model doors and other passageways (the topology) correctly. Simple subdivision does not cut it, the most coarse grained grid you can get away with needs to be detailed enough to at least qualitatively map the full situation. It's possible to get around that, but then your data structures get more complicated and your algorithm gets slower.

[elexis]

Hmm, back to the speed limitations again. The only other vague idea I can think of is instead of using a larger grid for further away, use a collection of linked nodes, one in the middle of every room which is linked to one in the middle of every entrance/exit of it. That way you would only need to (at least) use the grid for the room that you are in. Not particularly effective for large rooms or short trips, but for pathfinding from one end of the building to another it would be quite useful.

[martin]

Hierarchical pathfinding is a technique used in games, so it's certainly a possibility. But you have to think about generating your navigation grid/mesh, if you add a requirement for another form of map of the building that has to be generated when the building is, which slows down the generation step.