ZFG was developed in a custom engine built upon Java Development Kit and default libraries. The following news update gives insight into the procedural map generation systems and efficiency improvements that have been made over the past week, as well as a look into what’s coming up next.
Check out the weapons trailer to see it all in action:
Segment system: The maps are based upon a 2 dimensional grid of segments where each segment can be one of a variety of variants that were initially limited to the Forest, Military base, residential area, Business area, and Park. The segments have set walls and doors that are positioned to correctly correlate to the base images of the segment. Then environmental objects, loot and AI are then spawned based on predetermined positions with variation being added by random factors. The addition of loot is also affected by the difficulty that’s chosen by the player, which is done by increasing the likelihood that an item will be omitted from being generated for higher difficulties.
Map Generation:
The map segment variant at a set location is determined based on rules provided by the selected generation method, of which there are three. The first being Fixed generation. This loads a predetermined map that can be created and modified by the player to create a map of their liking. The second is simply to choose between the variants randomly but this can lead to excessive numbers of military bases that logic would dictate should be rarer than residential or other areas. Finally the main method is the Town generation which uses probability based rules to generate a random map that emulates the layout of a town. Town generation works radially, creating a roughly circular outline for the town, where in which the centre is predominantly residential and business areas. These then give way to less densely populated areas consisting of parks and residential, ultimately leaving farming and forested segments to the exterior that encircle the town in all directions. During this process hospitals and military bases are also added with much lower frequency to emulate their rareness. With hospitals being limited to the centre of town and the military bases being on the exterior. These generation methods work for any sized map and are different every time with the obvious exception of Fixed, although even fixed with have random AI, and loot positioning.
New Segments:
Recently the original five map segment variations have seen visual overhauls and improvements to the way in which items are added to them with particular emphasis on variation when playing of the different difficulties. In addition to this, two new segments have been added.
Hospital Segment
Farm Segment
Efficiency improvements:
Over the last week since the announcement of ZFG I have been focusing on efficiency, with particularly large focus on the AI, which with the need for environment detection, navigation and behaviours have had a large impact on performance when persistently simulated across the map in their hundreds. The main issue presented by having a large number of AI is that for each AI entity you must check if they are within range to interact with, or in the case of the physics system, if they are close enough to collide with every other entity. In a case where you have 1,000 AI that means you must do 1,000 * 999 checks (-1 as you don’t need each AI to check themselves). This is a problem as a large percent of these checks will result in the answer of no and as for every n AI there are n2 checks you end up with exponentially more checks for increasing numbers of AI which forces you to keep the numbers small. To combat this a grid system can be used as if each grid element is larger than the max detection range of any AI you know that the other AI in the same grid or surrounding eight grids will be potentially within range and as such you can assume all other AI are too far away reducing the number of unnecessary checks dramatically. As there is already a map segment system in place this was adapted so that each segment would store a record of its contents, including all AI, loot, environmental objects, explosions and bullets. When each item was updated they would finish by checking if they had moved to a new segment and would subsequently be moved into the correct segment if needed. The resulting change means that now each AI only has to check nine segments worth of other AI which will vary depending on the location but would typically average around 25 per segment giving a total of 225 AI that are feasibly in range that each need to be checked. This average is constant regardless of whether you increase the map size or total number of AI, so for every n AI there are typically on n*225 checks which only expands linearly when we increase the number of AI.
The newly implemented grid based culling and other changes boil down to an approximate increase of 1,200 AI to over 5,000 with the same performance cost.
Multi-Threading:
In addition multithreading was implemented into the map simulation which includes all physics interactions and AI functionality. This essentially means that rather than taking a sequential approach where each task must be completed before starting the next, the system can instead, take advantage of multi-core CPUs and do multiple things at once. This is currently done by dividing the map segments into four groups after cutting the map in half both vertically and horizontally. Each group can then be handled on a separate thread before allowing them all to finish and return control to the main thread, which then continues with rendering. There are more complex ways to implement multithreading but even this has resulted in the previously 5,000 AI limit being extended to a whopping 16,000. All of which are constantly simulated with physics and their respective AI behaviours.
So, all in all, going from 1,200 to 16,000 AI is not bad for a little over a week, and is resulting in some really interesting developments for the core game.
As a final note, int the next week or more I will be focusing on multiplayer functionality that will use a player hosted system not too dissimilar to other java based multiplayer games such as Minecraft. I’m very excited to be finally working on full multiplayer integration, especially with the smaller initial tests going so well. So look forward to new updates in the future and a soon to be released playable demo.
Keep up to date on development news by following me: @ZombieFluidGame
