DISCLAIMER: All of the content below is heavily conceptual and may never be in the game. All images and text are stand-in. Please read this before taking the images out of context!
Region Zones Design
With update 29, we wanted to make territory conquest progress feel more granular. We also wanted to make better use of the world space. To this end, we decided to break each region up into zones. Each zone would be based around a major Map Marker and would contain a Town Hall or a Fort.
Now, we could create the zones by hand for each map. However, given the sheer number of maps we have and the fact that our maps can change fairly frequently, it becomes extremely inefficient do this sort of thing manually. Just like the map image generation process that Adam spoke about in Devblog 71, we needed a programmatic solution to generate the zones.
Voronoi Diagram
Definition: https://en.wikipedia.org/wiki/Voronoi_diagram
Interactive Demo: http://alexbeutel.com/webgl/voronoi.html
Key terms
Site: A key location or point on the plane that cells are generated around.In our case these are the major Map Markers.
Cell: A subdivision of the plane that contains exactly one site.
Edge: Lines separating and enclosing the cells.
A Voronoi diagram is a way to break a plane apart into cells, given a set of sites on that plane. The cells or zones are created such that for each point within the cell, the closest site to the point is the site that the cell itself is based around. Try playing around with the demo linked above to gain an understanding of this. Note that the lines (edges) that are generated bisect the space between 2 points precisely. The edges around the cells are formed by sets of points that are equidistant to the 2 adjacent sites the edge is between. A Voronoi diagram generated with each major map marker as a site was exactly what we needed to create the region zones.
Implementation
Listed below will be two approaches to generate and render region zones based on the rules of a Voronoi diagram.
This was an extremely rough first pass of region zones. The pseudocode for what’s happening to render this image is as follows
Zone generation:
Iterate over every pixel for a given map. For each pixel:
Find the closest major Map Marker.
Add the pixel to the zone for that map marker.
Rendering:
Iterate over the Map Markers
Draw all the pixels within its zone as a predefined colour for that zone.
Now this works exactly as the voronoi diagram is defined. Each zone contains the points that are closest to the zone’s major map marker. However, it is extremely slow because it has to iterate over each pixel and then iterate over each site for each pixel. The complexity of this algorithm is N^2. It would not be feasible to use this approach in the live game without causing a significant impact on frame rate. We needed a more efficient algorithm to generate the Voronoi diagram. This led us to Fortune’s algorithm.
Fortune's Algorithm
Explanation + Demo: https://jacquesh.github.io/post/fortunes-algorithm/
Input: A list of sites
Output: A list of edges around each site
I won’t go into too much detail here since the algorithm is quite complicated. The demo linked above has a great visualization for the process. To summarize, a parabola is generated with each site as its focus. As the parabolas intersect, they form straight edges. As edges intersect other edges, they are cut off. These edges start forming polygons around the sites. These polygons are the voronoi cells we are looking for. A collection of these edges is the raw output of this algorithm.
The raw edges generated for Deadlands is rendered below:
As you can see, the inner zones are formed perfectly. The edges for the zones intersect and form a polygon around each site. These are the voronoi cells - the region zones. However, the outer zones have edges that extend beyond the bounds of the map. Some intersect outside the map boundary and some extend to infinity since they never intersect with another edge. The voronoi algorithm actually has no notion of the bounds of the plane it’s operating on. All it knows about is the positions of the sites. It certainly has no idea about our hexagonal map boundaries. So we need to do some work to create meaningful zones out of the generated edges.
To start, we need to clamp the edges to the border of the map. To do this:
We find the point where an edge intersects one of the lines that form the hexagon for the map.
Then we change the endpoint for the edge to be the intersection point.
The result looks like this:
If you look closely, you’ll notice that the vertices of the hexagon and are actually missing. Again, this is because the voronoi diagram has no idea about our hexagonal maps.
To fix this:
We iterate over the vertices of the hex. For each vertex:
Find the closest site and add the hex vertex as an additional vertex for the polygon for that cell.
Now we have the fully formed region zones, constrained within the hex border.
All that remains to be done is to colour the zones according to the faction that owns it:
Day and Night
Game development is strange and, sometimes in the middle of a pipeline, quality of life or polish features manage to creep in. It’s often the first thing any dev wants to do, but usually the last we’re able to work on. Way before the bulk of the work on the fall update got into full swing, a programmer asked me, “hey, what do you want to do in-game at night?”
At first, I didn’t really understand what he was talking about? Like what do you mean, what do I want to do? Like, sneak around some FOBs, what are we talking about? Turns out, while critical features were still in the planning phase, they managed to sneak in some hooks for guys like me to use. So now we have an event for the engine to know when the game is currently daytime or night. You may be surprised to learn that this—like so many other things in game development—isn’t as simple as it is on paper.
Either way, there are a lot of things I want to do. Firstly, lights shouldn’t really just burn all day and night. There could be lots of different structures in the world with different kinds of lights that are toggled between day and night. Conversely, there could be player-controlled spotlights/etc. that are only really useful during the night. Flares are a pretty good start; I think this particular mechanic can really help to differentiate the play-styles between day and night.
Other fun little things I’d like to see are insects. Different varieties of insects that appear during the day, such as flies, cockroaches, and at night, maybe fireflies. Fundamentally this shouldn’t be that hard to implement, just requires extra time. One area of brainstorming I’ve had some trouble with is how snowy areas are affected. In reality, aside from a few wintry birds or big animals, there isn’t much life in snowy regions so not much changes between day and night. Except, of course, temperature.
Something I was able to sneak in: different ambient sounds between day and night. It always really bothered me that there were birds and seagulls during the night or crickets in some areas during the day. For a while, I thought about just putting the sounds on a timer, but things like that can get a bit tricky. If for some reason, it ever gets out of sync, you’d just have it flip eventually, and that’s arguably more annoying.
So, I want to extend a question out to all of you: what kinds of fun little features would you like to see between day and night? Small additions like these help bring Foxhole to life on the slow march to 1.0.
Deployment System
In Update 29, we made a lot of changes to the way spawning works. Specifically, fast travel and the rules for home bases have changed tremendously. Our goal with these changes was to remove the flaws of the previous system and to make the system a bit more strategic, with players deciding where fast travel points should exist rather than the game doing it on your behalf.
I wanted to shed some light on the details of how the new system works. Below you can find a more detailed breakdown on all the rules of this system. Keep in mind there were a LOT of corner cases to contend with (queues, griefing, server topology, gameplay, etc) when designing this system so there were many constraints put on what we could and couldn’t do.
A shout out to Phil for providing this detailed breakdown below
Spawn System Rules
■ Home (AKA Star) Bases and infinite respawns have been removed.
■ Wild spawning has been removed.
■ Players now have 2 spawn points that can be set independently:
○ Home Base
○ Forward Base
■ Home Base spawn points include:
○ Town Halls
○ Frontier Bases
○ Deployed Landing Ships
■ Forward Base spawn points include:
○ Forward Operating Base
○ Keeps
■ When spawning at your Home Base, you Forward Base spawn point is cleared.
■ You can spawn at nearby Home Bases if your Home Base spawn point is destroyed.
■ You can spawn at a nearby Safe house if your Home Base and Forward Base is destroyed.
■ You are always given the return to the Home Region when selecting your spawn.
■ One soldier supply is always required when respawning.
■ Respawning in other regions works as it did previously.
Deployment System Rules
■ Certain Bases can now be deployed to directly from the Home Region, provided they have a non-zero Garrison Size
■ When a player travels to a deployable Base, Garrison Size is consumed and their Home Base spawn point will be set there.
○ Garrison Size is a consumable that automatically increases over time based on the amount of Garrison Activity.
○ Garrison Activity is based on the number of people operating in that region who have their spawn point at that location.
○ Garrison Size increases quicker for structures with Small/Large Garrison facilities, and for Frontier Bases/Deployed Landing Ships, and will gradually decrease overtime for abandoned deploy points.
○ Deploying in quick succession is limited and cannot be spammed.
■ Deployable Bases include:
○ Town Halls
○ Frontier Bases
○ Deployed Landing Ships
---------------
Foxhole Devstream 2pm EST - Every two weeks (alternative between blog posts) Tweet Devstream questions to @Matt directly on Discord or Twitter