It's all in your head, Part 19

The only place you'll ever hear the truth
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:36 pm

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.
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:54 pm

I suppose it depends on how the map is generated, but if the map is created on a room-by-room basis as opposed to walls growing out of nowhere and linking together then it should be very quick and efficient to create a node per room and entrance and link them together.
User avatar
martin
level5
level5
Posts: 3210
Joined: Fri Nov 19, 2004 8:37 pm
Location: ::1
Contact:

Postby martin » Thu May 06, 2010 2:27 pm

From the way I read Chris' earlier posts, and how I myself would build a system, I imagine it's hierarchical, so you start off with a floor with no rooms defined, and then as you need more detail rooms get added etc. That kind of system is probably pretty much perfect for generating a coarse waypoint map as you add more detail. Depends if it's done exactly like that though.
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:52 pm

elexis wrote:I suppose it depends on how the map is generated, but if the map is created on a room-by-room basis as opposed to walls growing out of nowhere and linking together then it should be very quick and efficient to create a node per room and entrance and link them together.

What you are describing is basically the path-finding algorithm from Darwinia---units travel node to node. Chris discusses this method in the first post, and, I think, dismisses it.

xander
User avatar
martin
level5
level5
Posts: 3210
Joined: Fri Nov 19, 2004 8:37 pm
Location: ::1
Contact:

Postby martin » Thu May 06, 2010 3:04 pm

He's describing it as a higher level algorithm though, which is fair enough, a first pass coarse darwinia style waypoint map which just plots which rooms and corridors you need to walk down, and then the grid based system can be calculated as the AI is walking that path. So in that case you can spend a short amount of time calculating your general path, say 0.1 seconds, and then spread the 1 second of pathfinding which chris mentions over the next minute or two as you walk the path. Also has the advantage that as you walk the path your destination can change, or you can navigate sudden obstacles and only dispose part of the path, not all of it.
GENERATION 22:The first time you see this, copy it into your sig on any forum and add 1 to the generation. Social experiment.
omicron1
level0
Posts: 4
Joined: Sat Jul 28, 2007 9:21 pm

Postby omicron1 » Thu May 06, 2010 11:19 pm

Suggestion, if you haven't already thought of it:

Add another value to the stored information in your 2D grid, to wit, areas. Assign each cell a value, and let values spread from cells with higher values to those with lower values, with walls being marked off as impassable for spreading. (Alternatively, flood-fill areas until there are no valueless areas left) When this has iterated itself as many times as possible, you'll be able to eliminate that worst-case scenario problem; this would also make it relatively easy to remove blocks (as many as a pair of floodfill operations) or add them (floodfill with a lower value on one side of a new filled grid spot). This is really an essential improvement for any pathfinding situation involving static terrain (for instance, making RTS pathfinding run fast on a huge map), and could come in handy here too.

Larger grid idea: Octree subdivision.
You can't use an evenly divided grid (as in, an array/matrix), but it allows for as large as possible squares for pathfinding purposes.
UnDeR_SEEG
level0
Posts: 9
Joined: Thu Mar 04, 2004 1:34 pm

Postby UnDeR_SEEG » Fri May 07, 2010 12:53 am

It's been really good to follow this game, more people should blog this level of detail during development.
I <3 procedural content
User avatar
KingAl
level5
level5
Posts: 4138
Joined: Sun Sep 10, 2006 7:42 am

Postby KingAl » Fri May 07, 2010 1:14 am

It is looking rad. (I wish I had something more interesting to say.) I really enjoy reading about the problem solving process and getting a bit of a vicarious "Eureka" when you come to a nice solution :P The heat/sense map idea reminds me of the Pac-man ghost AI.
Gentlemen, you can't fight in here: this is the War Room!
Ultimate Uplink Guide
Latest Patch
Lowkay
level1
level1
Posts: 14
Joined: Sat May 19, 2007 9:17 pm
Location: UK

Postby Lowkay » Fri May 07, 2010 7:26 pm

What happens with your 2D map when you're handling multiple stories.
For instance many buildings have some levels that are divided, i.e. you cannot move from one side of the building to the other. They have multiple stairwells for each side. Other levels have no such divide. So what happens when you're standing next to one stairwell on an open level and want to go down to the level below but on the other side of the divide?
A* level by level would not be able to solve this, i.e. it would take you down to the next level on the stairwell closest, but then it could not get you across the divide at the correct level to where you want to be.
Ok there are easy workarounds to this problem, but they require more than just a single level 2D map.
User avatar
elexis
level5
level5
Posts: 1466
Joined: Fri Aug 24, 2007 6:11 am
Location: Australia
Contact:

Postby elexis » Fri May 07, 2010 11:47 pm

He did mention that he this system was mainly for a single floor, but again, if there was a pre-existing node system in place it would be quite easy to plot a path over multiple floors (although you might want to set up some sort of priority-based system to make sure that regular workers prefer lifts and agents prefer stairs etc.
User avatar
GreenRock
level4
level4
Posts: 512
Joined: Sun May 03, 2009 3:47 pm
Location: Triangulating...

Postby GreenRock » Sat May 08, 2010 2:18 am

I don't understand how any of this applies to the city generator we were all raving about a few months ago.
User avatar
martin
level5
level5
Posts: 3210
Joined: Fri Nov 19, 2004 8:37 pm
Location: ::1
Contact:

Postby martin » Sat May 08, 2010 2:27 am

well, what he just showed us is set in a building. Cities are composed of buildings. The city generator generates cities.

Go figure ;)

Seriously. How I suspect things will work is the procedural generator fills in the "gaps" in missions. So, for example, you could hand build an entire bank in your map and tell the generator to build the rest of the city. Or maybe you handcraft just the bank vault and tell the generator to build you the rest of the rooms, and he rest of the city. Or maybe you don't bother with that, you just tell the generator to build you a city which has at least one bank. So you can be very flexible in your missions and their layout - the more you leave to the generator the more re-playability value the mission has.
GENERATION 22:The first time you see this, copy it into your sig on any forum and add 1 to the generation. Social experiment.
RabidZombie
level5
level5
Posts: 2414
Joined: Fri Nov 18, 2005 10:09 pm

Postby RabidZombie » Sat May 08, 2010 9:11 am

martin wrote:well, what he just showed us is set in a building. Cities are composed of buildings. The city generator generates cities.

Go figure ;)

Seriously. How I suspect things will work is the procedural generator fills in the "gaps" in missions. So, for example, you could hand build an entire bank in your map and tell the generator to build the rest of the city. Or maybe you handcraft just the bank vault and tell the generator to build you the rest of the rooms, and he rest of the city. Or maybe you don't bother with that, you just tell the generator to build you a city which has at least one bank. So you can be very flexible in your missions and their layout - the more you leave to the generator the more re-playability value the mission has.


Lets not forget the plans for the generator was to generate the buildings as well. And the fact it's a spiritual sequel to Uplink. I think we may play in a persistent world (like Uplink) where every building is generated beforehand.
User avatar
martin
level5
level5
Posts: 3210
Joined: Fri Nov 19, 2004 8:37 pm
Location: ::1
Contact:

Postby martin » Sat May 08, 2010 12:35 pm

Well you can seed a procedural generator based on some non changing value, which effectively gets you a persistent world. Which would mean that you can use the same mission over and over (just like uplink did) but with different rooms/buildings/cities being generated around the handcrafted parts of the mission, which would make it feel different every time
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
GreenRock
level4
level4
Posts: 512
Joined: Sun May 03, 2009 3:47 pm
Location: Triangulating...

Postby GreenRock » Sat May 08, 2010 8:33 pm

I figured the city will act as a chess board.
Whenever you are to move a piece (obtaining a level of a building, or an entire building for that matter), you have to go through the process of actually capturing the place you want to move to.
You do this by hacking, infiltrating the level of a certain building. Then, certain other areas are open to be infiltrated. This can be used for multiplayer...

Return to “Introversion Blog”

Who is online

Users browsing this forum: No registered users and 9 guests