It's all in your head, Part 19
-
- level1
- Posts: 12
- Joined: Sat May 30, 2009 10:45 pm
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!
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!
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.
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
- level5
- Posts: 10803
- Joined: Thu Dec 07, 2006 9:46 pm
- Location: The Multiverse
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?
Smoke me a kipper, I'll be back for breakfast...
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.
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.
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
- Chris
- Introversion Staff
- Posts: 1172
- Joined: Sat Nov 25, 2000 7:28 pm
- Location: Cambridge, UK
- Contact:
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.
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.
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)
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)
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?)
(Am I ignorantly talking rubbish?)
- bert_the_turtle
- level5
- Posts: 4795
- Joined: Fri Oct 13, 2006 6:11 pm
- Location: Cologne
- Contact:
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.
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.
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.
GENERATION 22:The first time you see this, copy it into your sig on any forum and add 1 to the generation. Social experiment.
Who is online
Users browsing this forum: No registered users and 7 guests