Introversion

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.

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.

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

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.

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.

It's been really good to follow this game, more people should blog this level of detail during development.

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 The heat/sense map idea reminds me of the Pac-man ghost AI.

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.

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.

I don't understand how any of this applies to the city generator we were all raving about a few months ago.

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.

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.

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

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...

This is looking really great. So nice to see an update and to see how far it has come along. Having a procedural world simulated to this level makes for some really exciting possibilties. Can't wait! :p