In-Depth: Walking In The Void

[In this reprinted #altdevblogaday in-depth piece, former KmmGames senior game programmer Michael Carr-Robb-John looks at how to make A.I. characters move around in areas of your world that aren't currently loaded.] Building systems that allow A.I. characters to move intelligently around an environment is a common challenge encountered by game play programmers. One of the main data requirements needed to do this is a level map of some kind, it might be a grid of squares or more common these days a navigation mesh. However when this information is missing or un-available as can happen in a streaming world how can you make A.I. characters walk around in places that are not currently loaded? Let's consider an example scenario, here is our demonstration world (click for a larger image): Steamed zones are indicated by the named sections and the only zones that are loaded in memory are those that are directly connected to the players current location. Let's say that the player is standing in the blue zone "Central Court". The currently loaded zones are Central Court, Guard Room, Drawbridge control room, Kitchen, Entrance hall, and Barracks. An enemy A.I. Character is guarding the grounds of the castle by walking a patrol from the "Clerk's Office" to the "Audience Chamber" and then to the "Guard Room".

Navigation Solving this scenario given that parts of the navigational mesh might be missing or at times completely non-existent requires, for lack of a better phrase, a mini-map. The mini-map contains which zones are connected together and apart from some additional data I will talk about later it would pretty much look very similar to the demonstration map above. It always exists in memory and hence is always available regardless of which zones are currently loaded. In a traditional navigation system you would provide the x, y, z coordinates of where the character currently is and specify the x, y, z of where you want to go. The returned route would be a list of optimized waypoints that the character's piloting system can use. Plotting a route from Start position to Goal on a navigation mesh:

Navigation Route:
      Waypoint 1 - [X, Y, Z]
      Waypoint 2 - [X, Y, Z]
      Goal - [X, Y, Z]

With a streaming world we now require an additional parameter for each coordinate, the zone identification. Navigation changes slightly, it now becomes a two phase process. The first phase calculates a high level route based upon the mini-map, in order to do this the mini-map needs a few more bits of information than simply which rooms are connected together. It needs to know the location of all entry / exit points for each zone, as well as the piloting distance from each point to every other point in that zone. The more accurate the distance calculation is, the better results you will get from this system. Hence why the piloting distance is best, the worst case value is the direct distance between the two points. There are reasons that might prevent accurate piloting distances being worked out, i.e. the zone design isn't one that allows a route to be plotted because of moving platforms or barriers, etc. The diagram below indicates the sort of information that is required for each zone, it's entrance / exits and the distances from that point to every other point. With all the data stored in the mini-map it now becomes possible to calculate the quickest route from one room to another using your favorite search algorithm. Looking at the scenario example of a guard traveling from "Clerk's Office" [sX, sY, sZ] to the "Audience Chamber" [dX, dY, dZ] the first phase navigation would generate the following path:

Navigation Route:
      Clerk's Office – 60m
      Great Hall – 40m
      Entrance Hall – 30m
      Waiting Room – 25m
      Audience Chamber
      Goal - [ X, Y, Z ]

The second phase takes the high level route and if any zone is actually resident in memory it will convert that part into a normal navigation route. The route in our example would be expanded like so:

Navigation Route:
      Clerk's Office – 60m
      Great Hall – 40m
      Entrance Hall - Enter [ X, Y, Z ] (These coordinates come from the mini-map)
      Waypoint 1 - [ X, Y, Z ]
      Waypoint 2 - [ X, Y, Z ]
      Waypoint 3 - [ X, Y, Z ]
      Entrance Hall – Exit [ X, Y, Z ] (These coordinates come from the mini-map)
      Waiting Room – 25m
      Audience Chamber
      Goal - [ X, Y, Z ]

Of course as zones come and go this can have a knock-on effect to the generated routes, expect to have a mechanism in place that triggers an update/refresh of the generated routes if a zone gets loaded or unloaded. Piloting Piloting  is the process of actually moving a character along the generated navigation route usually applying some form of dynamic obstacle avoidance as it goes. In many respects piloting through zones that are not loaded is very simple, just wait for a certain amount of time to expire. The duration is dependent upon how fast your character moves, if he or she moves at 1m/s, then it will take a character 15 seconds to walk the 15 meters from zone entrance to zone exit at which point you then move onto the next zone. If the next zone happens to be loaded you simply relocate the character into the world at the door position and use your normal piloting techniques to move the character to the exit door, where the character disappears (leaves the zone) and continues traveling the unloaded zones again. Now what happens if the character is walking through an unloaded zone when it gets loaded? Let's say the character had got 7.5 seconds inside the zone and it was supposed to take 15 seconds to travel? Well that is actually halfway along the path, build the waypoints for the room from entrance point to exit point and actually snap the character to halfway along the path. It's not an exact process but you will find that it is a pretty good estimation, the only time this might fail is if there is no valid path from the entrance to the exit in which case you must have a fail safe option and that will be dependent upon your actual game. Generating The Mini-map In order to auto generate the mini-map I have a game entity called a Zone Marker, one of these markers is placed at each entrance / exit point in every zone, the marker contains information of what zone it leads too. When each Zone is built I take the Zone Markers and do a traditional A* from each marker to every other marker on the zone navigation mesh. This gives me the distances between each entrance / exit point which I can then update to the Mini-map. Additional data you might want to include in the mini map is if certain routes can become blocked for example because of a passage collapse, locked door, etc. As long as the state of the connection can be verified without loading a specific zone, then you can apply that to the first phase route generation. I usually have a section in my global data manager that stores the locked / unlocked state of all doors and connection states in the world for this purpose. As I mentioned earlier, it is possible when calculating the piloting distance from one entry / exit point to another that there is no path available. There are various solutions I have used in the past but it all really depends on what is actually contained in the zone. I usually set a flag on each zone marker on how to deal with these scenarios since that allows me the most customization. The options I have supported are:

A Traditional Solution Another way that this can be achieved of course is by doing it manually using event timers and scripts to trigger character appearances, etc. Sometimes when you don't have the time or resources available this can be a good solution, even more so if you only have one or two cases where characters need to appear to achieve world movement. [This piece was reprinted from #AltDevBlogADay, a shared blog initiative started by @mike_acton devoted to giving game developers of all disciplines a place to motivate each other to write regularly about their personal game development passions.]