It's all in your head, Part 19

The only place you'll ever hear the truth
User avatar
xander
level5
level5
Posts: 16869
Joined: Thu Oct 21, 2004 11:41 pm
Location: Highland, CA, USA
Contact:

Postby xander » Wed May 05, 2010 4:13 am

elexis wrote:Don't know about the A* thing, but the male/female toilets are definetely not on a common wall here, although vertically (ie between levels) all the toilets line up.

It may just be an American thing. What about the rotation of the toilets? Should they at least be rotated so that the tanks are all on the same wall?

xander
User avatar
elexis
level5
level5
Posts: 1466
Joined: Fri Aug 24, 2007 6:11 am
Location: Australia
Contact:

Postby elexis » Wed May 05, 2010 4:22 am

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
level1
level1
Posts: 12
Joined: Sat May 30, 2009 10:45 pm

Postby Lord Ozymandias » Wed May 05, 2010 5:01 am

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!
User avatar
martin
level5
level5
Posts: 3210
Joined: Fri Nov 19, 2004 8:37 pm
Location: ::1
Contact:

Postby martin » Thu May 06, 2010 12:48 am

xander wrote: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.

xander wrote: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...
GENERATION 22:The first time you see this, copy it into your sig on any forum and add 1 to the generation. Social experiment.
User avatar
elexis
level5
level5
Posts: 1466
Joined: Fri Aug 24, 2007 6:11 am
Location: Australia
Contact:

Postby elexis » Thu May 06, 2010 1:00 am

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.
User avatar
Ace Rimmer
level5
level5
Posts: 10803
Joined: Thu Dec 07, 2006 9:46 pm
Location: The Multiverse

Postby Ace Rimmer » Thu May 06, 2010 1:20 am

martin wrote:
xander wrote: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? :P
Smoke me a kipper, I'll be back for breakfast...
User avatar
martin
level5
level5
Posts: 3210
Joined: Fri Nov 19, 2004 8:37 pm
Location: ::1
Contact:

Postby martin » Thu May 06, 2010 1:26 am

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.
GENERATION 22:The first time you see this, copy it into your sig on any forum and add 1 to the generation. Social experiment.
User avatar
xander
level5
level5
Posts: 16869
Joined: Thu Oct 21, 2004 11:41 pm
Location: Highland, CA, USA
Contact:

Postby xander » Thu May 06, 2010 2:20 am

martin wrote: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
User avatar
Chris
Introversion Staff
Introversion Staff
Posts: 1172
Joined: Sat Nov 25, 2000 7:28 pm
Location: Cambridge, UK
Contact:

Postby Chris » Thu May 06, 2010 7:14 am

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.
User avatar
martin
level5
level5
Posts: 3210
Joined: Fri Nov 19, 2004 8:37 pm
Location: ::1
Contact:

Postby martin » Thu May 06, 2010 9:39 am

So the entities do something like that valve paper described, approximately following an artificial looking path which results in a natural looking movement?
GENERATION 22:The first time you see this, copy it into your sig on any forum and add 1 to the generation. Social experiment.
User avatar
elexis
level5
level5
Posts: 1466
Joined: Fri Aug 24, 2007 6:11 am
Location: Australia
Contact:

Postby elexis » Thu May 06, 2010 9:57 am

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)
User avatar
martin
level5
level5
Posts: 3210
Joined: Fri Nov 19, 2004 8:37 pm
Location: ::1
Contact:

Postby martin » Thu May 06, 2010 11:14 am

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...
GENERATION 22:The first time you see this, copy it into your sig on any forum and add 1 to the generation. Social experiment.
User avatar
elexis
level5
level5
Posts: 1466
Joined: Fri Aug 24, 2007 6:11 am
Location: Australia
Contact:

Postby elexis » Thu May 06, 2010 11:27 am

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?)
User avatar
bert_the_turtle
level5
level5
Posts: 4795
Joined: Fri Oct 13, 2006 6:11 pm
Location: Cologne
Contact:

Postby bert_the_turtle » Thu May 06, 2010 11:35 am

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.
User avatar
elexis
level5
level5
Posts: 1466
Joined: Fri Aug 24, 2007 6:11 am
Location: Australia
Contact:

Postby elexis » Thu May 06, 2010 12:19 pm

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.

Return to “Introversion Blog”

Who is online

Users browsing this forum: No registered users and 11 guests