So I'm on the long road to a first alpha right now. And by alpha I mean an actual alpha and not the "alpha" you see on Early Access these days (which means anything from an actual alpha to a finished game). That means getting the state machines bug free and reaching a point where I can start iterating on game design.
For now the features include: collecting resources, building structures, goods/food consumption, basic management of labour through work orders and labour assignment. These would constitute a game that is roughly equivalent to a Dwarf Fortress clone. After that I'll slowly introduce technological research, uprooting/planting of vegetation, AI factions and then diplomacy.
It's a short post since there's not much to talk about when you're bug squashing.
A lot of the joy from an economic game is watching your industries go ahead after you've set them up. One issue that usually stands out is storage of goods. A game like Cultura is really complex, it has fifteen types of raw items and perhaps upwards to thirty finished and intermediate goods (the exact number is still in flux). This gives us two immediate questions: How many types of storage buildings for the different goods? How many sizes of storage buildings of each type?
For Cultura, the question of types of storage buildings is going to be simplified to "food" and "not food". This is mostly because in the game, the idea of useful storage is more about accessibility, space and preventing spoilage. Only food spoils, so its storage is paramount. Everything else is not really much of a concern so they're mostly for space efficiency (piles of goods would generally be less efficient than a storage pit). Then perhaps there's just two sizes of each: big and small. That leaves us with just four types of storage buildings and then upgrades for them as you progress in technology.
Algorithmically interesting is how you decided which storage site to use to drop off your goods and how you coordinate the movement of goods between storage sites. This is where you get the "sit back and watch" comfortable feeling of an economic game. The current idea is to use a "big cup small cup". A worker chooses the closest drop off site to dump goods. Then when a storage location is full, if it has a larger storage location to transfer goods into then it'll queue up a goods transfer job. This means a small cup can be poured into a larger cup. Whether or not goods should transfer between same size cups is still questionable (right now the answer is no, that way any number of storage location sizes can be coded and people simply keep transferring only "upward").
The title is a pun because there is a movie with a similar name. Hurr. Anyway, Cultura, when it's good and ready to be released will involve farming. The end game will be the neolithic time period so the hope is that you'll be fascinating with min/maxing your empire, engaging in endless diplomatic schemes and building wonders. Also trading with distant lands and marching armies. But back to farming, the lithic time period of humans is probably split between pastoral societies and agrarian societies. There's some mixture but what's important here is getting down to the basics.
This is a simulation game of building up a society from the ground up and so the best place to gather numbers for game mechanics is the real world. Cultura is a game where it doesn't tell you what works, what doesn't and what policies get you what bonuses, instead you do what you want and then the simulation takes care of the effects in a natural manner. With farming, it means that the land production values are going to be design something along the lines of real life.
Okay, let's look at agrarian production rates:
223 kg/ha in Han Dynasty based on a statement from an official commenting on unfairly high tax rates
442 kg/ha in Qin Dynasty based on a statement from an official commenting on new farming methods
1431 kg/ha in Egypt Middle Kingdom based on a priests's statement on what a "good harvest" would be
714 kg/ha to 1429 kg/ha in Egypt New Kingdom based on some records from archaeologists
So that varies a lot and the Nile is especially productive. That's not a surprise; China's Yangtze is not going to be good competition against the floodplains of the Nile. We could probably average the Egyptians to be around 1000 kg/ha. The Chinese number is harder to judge but perhaps we could just take an average and say it is 300 kg/ha.
That brings us to pastoral societies. What kind of food production might one expect from herders? And for that matter, animal meat production.
1.16 kg/ha meat + ?? kg/ha milk for the Borana
That data... is a little sparse but there's little data gathering for pastoral societies. For the Borana, there's around 1162 kg/ha dry mass produced from the land they live on, on average per family, including the wet/dry areas they might move about in. They mostly rely on milk products to survive and their population density is exceptionally low. Each person lives on around 43 kg of meat per year plus a lot of dairy.
Lastly, we want to look at what animal production would be for grain-fed farm animals. This is important for mixed farming (where you do both herding and growing crops). These numbers come from a Stanford study:
Cattle: 8:1 feed to mass ratio, 20:1 feed to edible mass ratio
Pork: 7.3:1 feed to mass ratio, 4:1 feed to edible mass ratio
Chicken: 4.5:1 feed to mass ratio, 2.5:1 feed to edible mass ratio
Milk: 1.1:1 feed to mass ratio, 1:1 feed to edible mass ratio
Fish: 3:1 feed to mass ratio, 1.8:1 feed to edible mass ratio
These are fairly rough numbers and what they translate into game design here is relative values. So we want good arable land to produce around 200-400 units of food per square area, we want dryland to produce around 1100 units of dry mass for fodder per unit area, and we want a conversion ratio of grain feed or wild forage in the table above. Dryland would be unsuitable for growing crops, while floodplains would be super productive at 700-1400 units of food per unit area. We could translate this to being something simple like: dryland produces 1100 dry fodder per square per year or 50 units of cereal (so not worth it), grassland produces 450 units of cereal per year (or perhaps 1500 dry fodder?), floodplains or other super area produces 1000 units of cereal per year (and perhaps 2000 fodder?). Looking at data for dryland crops however appears to show that they can have quite good yields and especially during ancient times they may have rivalled the twentieth century yields (though I suspect that it was unsustainable and led to destruction of soil fertility since they would not have had access to many other technologies that could have kept up soil fertility).
I think perhaps I may simplify soil fertility or I may not, it depends on the sort of decisions it can give the player. If I bring in the concept of soil fertility, the idea is that certain technologies can maintain the fertility levels (such as the application of manure) but ultimately the land plus the technology determines the carrying capacity and going beyond this is a short term gain at a long term cost.
Soil fertility might be some value which decreases per unit harvested off of the land, increased by technological tools (such as manure) up to the max of what that technology can provide and there is some natural regrowth (and maximum). That model gives a very simple way of expressing responsible land use to the player, something well studied throughout history (accidental over farming leading to exhausted soil and then agricultural collapse) yet is still very very lenient because it doesn't consider fertilizer run-off causing algae blooms, deforestation leading to changes in the water cycle, drainage of wetlands leading to flooding and so on. I'm not quite building a weather simulator here but how far should I go to create the simulation to avoid sacrificing emergent properties that come out of environmental questions of how a society interacts with the land it lives on?
Deforestation can already be pretty devastating in the game. Wood is obviously a very useful resource but the growth rate depends on the number of trees. Chopping more trees gets you more wood but decreases the forest growth rate. It's similar to grasses and whatnot. Luckily, the player does not need to think about canopy cover and the like that prevents the soil from drying up from being overly exposed to sunlight. So your overgrazing won't lead to desertification but it does lead to loss of grasses and then your animals die of starvation, then you die of starvation.
Microactions, Parent Actions, Faction Actions, Family Actions
Microservices? Hah, just kidding. This isn't some web service SOA game. Because screw micropayment games. We're here to talk about the amazing and fascinating world of actions; the state machines that get your units doing the things you told them to do. In Cultura, it happens in a hierarchial manner: faction, family, unit. The short version is that when you queue up a big faction-wide action it then doles out unit actions to individual units. Some automated actions, like finding food for the family, are family actions which doles out actions to individual units within a family.
As it turns out, debugging this is super hard. A unit has a stack of actions to track what it should be doing, as each action finishes it pops and the next action in the stack is worked on. Every action has a simple shared interface so that the unit can processTick just by calling doAction on generic actions. Underneath, each action is a child class of UnitAction which has its own various states. But, big actions are complex. Something as simple as "harvest node" turns into a confusing mess of state transitions (what if my inventory is full? resource node is exhausted? I'm under attack? drop off location disappeared or is full?).
So, we go into refactoring code. The current round of refactoring involves devolving each action into "microactions". An action is now defined by three simple concepts: Exit Conditions, Stacking Conditions and the Action. A microaction is an action without Stacking Conditions.
Exit Conditions
In order to keep things simple, an action has clear exit conditions. By breaking things down to microactions, the exit conditions become very simple. Move action? If I'm there then exit. Build action? Apply enough labour and then exit. Drop off action? Drop off what I can and then exit. The larger actions usually wait until a microaction is finished for some its exit conditions and merely tracks the number of microactions successfully completed.
This requires a bit of paradigm shift within the code. Actions don't get wiped off the stack. There's a few edge cases where things get tricky (making sure that we keep track of resources used in the construction of an object don't get lost if a unit dies but they do get lost if the building they're in is destroyed/looted). Secondly, player initiated actions can get replaced or wiped but they need to only be of certain types of actions so that they don't hit those edge cases.
Stacking Conditions
For more complex actions, they are built using a variety of microactions. A single harvest action involves move actions, pick up actions, drop off actions and the actual harvesting itself. The core of a harvest action can be thought of as the "harvest" action. Everything else is a condition where we bump out of the action and do something else. In the case of microactions, we only ever exit; we never do any other action and therefore are atomic actions. In bigger actions, they may need to use a microaction to complete a task. By never wiping the stack, we can rely on the fact that no matter what happens between one action and the next, an action can be completed to the right conditions and we can safely pop.
A stack condition is something that is checked and if needed, a new action is stacked on the unit. For a harvest action, this may mean that a move action is triggered if the unit isn't close enough to a desired location. We can safely assume when this action completes we are at the right location. This is key. All actions can have any number of things happen before they actually complete. A move can be interrupted by another move, by a flee action or anything else but when the stack pops and goes back to the same move action, it does what we want it to do and when it is done we are assured we are in the right condition. And even if we are not, it'd hit the same stacking condition in the parent action.
As an example, say we are harvesting. We try to harvest but we hit "are we close enough" stacking condition. We aren't! So a move action is stacked. When that completes, we are at the node and can then do the harvest.
A more complex example: we are harvesting. We try to harvest but aren't close enough so we stack a move action. But then the player selects the unit to go chop a tree. Later when the tree has finished chopping, the unit is somewhere else entirely but it pops back to the original stacked move action. It then tries to move to the node before harvesting.
Action
Most of the actions involve some core action that it does. This is "harvest" or "drop off". However, some actions are merely just a collection of Exit Conditions and Stacking Conditions. Refactoring everything into simple if statements leaves the core of any action to be an incredibly simple and small amount of code. This is what makes the debugging super easy. State transitions are clearly defined.
The Future
At more well funded studios (ones with more than zero dollars) the state transitions and actions are usually data-driven. The engine defines a bunch of atomic actions and a whack of possible enter/exit conditions and/or triggers. Eventually, I would like to get Cultura to that point but the microaction refactoring is the first step. It makes a clear way for me to go ahead with the data-driven model. For instance, every "if statement" could instead be codified in a class with an interface that has a single bool function shouldContinue and the c++ code encompasses what it means but the data-driven part just uses labels like "check if inventory full/empty". Then actions are built dynamically on load time with arrays of exit and stacking conditions.
So, after the Alpha there's going to be some thought about how to build the opponents in the game: the AI. Most games are built using scripted AI and some limited heuristics in order for the player to compete against some rudimentary opponents. In games such as Civilization it's a make or break scenario; bad AI translates to a truly awful game experience. For most big budget games, ironically there's zero time/money for developing good AI, whereas for indie developed games, there's a lot more room for it. It's mostly because AI is about the most unreliable (timeline wise) aspect of a game to work on.
Cultura is going to use pre-trained AI. How much heuristics depends on how well the training goes but let's talk about the idealized world of having an AI trained from nothing!
The Metrics
The Cultura AI is going to be looked at from three different angles:
Data: What metrics is the AI going to rely upon and measure?
Score: This is a continuous game, so rather than a concept of winning/losing which the AI can train upon, it continuously checks itself against a score to see whether it is doing well
Actions: What is it that the AI actually has control over in order to attempt maximizing the Score?
The exact method used to maximize score could vary: using a perceptron or perhaps a multi-layer neural net or something more sophisticated would be the obvious choices. These can lead to different output values for types of actions and what to act upon. A highly scripted AI would be built similarly except that the metric -> action translation would be built by hand. In the case of a trained AI, it would rely on the Data and then produce an choice about which action to take.
Data
The data is one of the most important aspects of the AI. Choosing insufficient or irrelevant metrics will mean that the AI is not paying attention to the right things to make its actions. Some of the data is simple. It should know what land it owns, what resources are on that land at any given moment and the number of people. It might also try to track buildings, industrial buildings of different types, tools, weapons and military power. And finally, the more difficult to track is the relationship with each faction it knows about.
Non-renewable Resources: It should know about the current maximum draw rate and the current actual draw rate.
Renewable Resources: It should know about the current amount left, the rate of growth and the current draw rate.
People: It should know about the number of people, it might split them apart by labour skill
Buildings: It should know about number of buildings, industrial buildings
Goods: It should track number of tools and weapons available, by type and have more points for superior tools/weapons in a particular category
Military Power: It should track how powerful it's currently active military is
How might we track a relationship with someone? The issue is that an AI should be able to care that it has hostile neighbours. But how to do that?
Relationship Score
Military Power
Distance
We could track those two metrics for each known neighbour, have some interesting way of calculating distance (perhaps the closest distance between two land areas of the two factions) and then worry about the military power. Then, we could lump all this together for a total relationship score that is used for calculations... or we could leave it separate. Lumping it together makes it a bit easier for the "national AI" to make overall decisions. One hopes through training it figures out that highly hostile military powers near it means that it needs to defend itself against the enemy.
Score
Ultimately, any AI needs some kind of objective function or else it doesn't train against much. In the case of Cultura there is no winning or losing. It is a continuous game that you continue to play FOREVER. So, how might we picture this? I figure the simplest way is to see the game as a race with positions and you always want to be number one. So, how well an AI thinks it is doing depends on how well others are doing. This could make the AI pretty hard to train (though, another thought is to have opponents who are fake but always improving at a constant rate and try to train AI against this).
This means that we have a way of calculating score and then all the AI is trying to do is get one more point compared to the highest score.
The score is likely to be a function that is something like Total = Population * Happiness * Health + Wealth + Buildings + Land. Another option is to try to track population, health, happiness and wealth separately and have the AI try to be first place in each category.
Actions
And what is an AI without the ability to do anything? The main picture of the world to the AI is Labour Distribution. Oh ho ho, how communist! But more seriously, this is where the AI tries to decide economic activity to the best of its ability in order to cope with the world and become number one. Also, for those that might actually be concerned about a fully communist AI-run society, the future of Cultura involves a concept known as administrative cost which limits the amount the government can do (because any action it takes administration points thus it might be superior to leave some things to private hands).
Okay so one type of action is changing the amount of labour in a particular industry at the margin. Doing it at the margin is important because we don't want an AI that makes crazy decisions, we want one that edges a society toward the optimal solution in a finite amount of time. Another type of decision would be to expand or upgrade the industrial structures related to a particular industry. In a similar vein, it might decide to increase the number of tools being made for a particular industry to increase production.
But, the more difficult decisions comes from foreign interaction. Okay, so it's pretty easy to say "Gee my happiness is low, build some kind of luxury". Then it's more difficult to say what kind of good. But even if you were to decide that when would you figure out "Gee let's instead trade ivory figurines for wooden furniture because the comparative advantage makes this a superior choice than forming a domestic industry to do this?" One choice is to say that a generic action is "increase production of x" and then a subsequent sub-choice to that is "how to increase production of x" where "trade" is an action and then the sub-choice there is "what do I trade off and to who for this good?"
And then of course, there's raiding, war and peace. How to train an AI to be able to figure out when it should make these types of decisions? "Relationship metric is very low, attempt to fix this is triggered, peace is less costly than war" OR "Wealth Score needs to be improved, weak nation nearby, crush nation and take goods"
Conclusion
This is a pretty good start to the AI question. In the end, the most important thing is there to be an awesome AI that is interesting to play against and is highly intelligent. This is one of the few games where an AI who is really awesome at managing a society is totally okay. Striving for Nintendo Hard here.
There hasn't been an awful lot of work done on Cultura in the past few weeks due to other concerns (like my job :D ) but in any case, some progress was made. The calculation for placing down buildings was revamped and by revamped I mean it now works properly.
Industry
Other than that, some thought was put into how industry works. Right now it's pretty basic. You collect some resources and it becomes a good.
Grains -> Beer
Grains -> Flour -> Bread
But, what exact structure do I want out of Cultura? So I compiled my thoughts into a convenient list:
Each land region only has a set of resources. Each land region has a type that determines how much of each type it contains (Dry areas have more grass and animals, wet areas have more trees).
Each society will focus on making only a subset of the types of goods. This is determined by the Culture Tree they pursue. Someone rich in wood would choose more wood-based goods. Someone rich in earth would choose more earth-base goods.
For each society to develop uniquely and have access to a balanced number of goods, each resource type leads to exactly three types of goods, one type of intermediate good and is assisted by one type of tool and one type of factory.
The point of this design is that each society can have 6-7 goods they produce, easily understood by a player and encourage trade to benefit both societies. Or raiding, up to you. This lets you focus a society to produce specific goods, have clear-cut industries you work on and have trade routes that are obvious (I produce Red Clay Pottery and I trade with Oglandia for Blue Flower Potpourri). For the lithic ages, this mimics the kind of trading that would mostly occur: goods for different goods. In later editions of Cultura, the concept of comparative advantage would be more well developed (that's not to say it doesn't already occur in this game but concepts such as labour specialization, labour skill, industrial infrastructure heavily affect comparative advantage and encourage trade of similar goods).
So the concept is meant to be simple. While it seems wordy here, the player is simply presented with a set of goods that are available from their land. Based on that they would choose to invest Culture points into "buying" goods that they can definitely produce. Then they build up those industries like in any other game (Anno, Caesar, Children of the Nile)... as in they would expand resource collection, make more tools, build up workshops all to increase productivity. After that they can choose to overproduce in order to trade the excess to other societies.
Tools and Factories
Now onto productivity. Okay, so there's another list of ideas:
Tools
Workshop/factory
After a lot of thought and debate in my head, I've settled on something as simple as possible. Tools boost productivity. There'll be a tool per super type of good. What do I mean by super type? A super type would be something like "pottery", which might start off as "clayware" which becomes "pottery" which becomes "glazed pottery" and then becomes "lacquerware" and so on. All of these can be improved by the same type of tool. Your tech level determines the level of tool you produce. In my opinion, the "confusion" that arises from having lots of different kinds of tools comes from the UI. In my planned UI (which has yet to occur) is to have the industry management group goods and their respective tool together when doing labour assignment. This way you can quickly balance the number of tool makers to goods makers and have the correct flow of tools immediately.
I use the term factory loosely. I just mean a building that helps produce a particular good faster. It does it in one big way: it skips steps. For the cost of fuel you can skip a bunch of steps. So normally a production chain is like "Grain -> Flour -> Bread". Then a second tier good would be "Grain -> Flour -> Bread -> Fruitbread" (look, you try to come up with more advanced bread). So, Grain is harvested from grain fields. Flour is made from Grain using labour. Bread is made from Flour using labour. Fruitbread is made from Bread using labour and Fruit. But, what if you had the awesome technology of... Fire Pit? Well then, now you can skip steps! Fruitbread can alternatively be made from Flour and Fruit and Labour and Lithic Fuel. So you've skipped the step of making Bread and instead directly make Fruitbread. Imagine the labour savings!
As the game designer this means I need to balance the cost of Lithic Fuel against the time saving you earn from not making bread (if it takes a really long time to make Lithic Fuel then I need to make the Fire Pit more productive to make up for it).
For the first iteration of Cultura this doesn't seem like much. But imagine later down the line when it is something like "Metal -> Metal Bar -> Bronze Bar -> Steel Bar -> Fine Steel Bar -> Perfect Steel Bar", then something like the "Fan-blown Blast Furnace" which gives you "Metal + Coal-Fuel -> Perfect Steel Bar" would mean that a single unit of coal-fuel just skipped four steps which could mean enormous labour savings (5x less assuming each step costs the same). It's really about game balance.
Ecosystem
How about the ecosystem? Most games are designed after "keep building forever". Cultura is designed a bit differently. This is meant to be a game where you play a society from ground up. And when I say from ground up, I mean eeeeeeeverything. The ecosystem matters. Forests grow. Animals give birth. If I were simulating water sources in the first iteration, there'd even be rainfall. I try to keep it simple though. The number of plants and animals determines their growth rate. In real life, their interaction determines the growth rate. But all I'm trying to simulate is a carrying capacity.
How many resources you draw from the ecosystem is limited by your land and your technology. Better land or better technology lets you draw more from the land. You can choose to underdraw to keep the ecosystem healthy or you could choose to overdraw for some purpose of prestige or fighting hostile societies, as a temporary measure. Or you might sacrifice the ecosystem of some land regions because you're not going to farm there anyway due to urbanization. It's up to the player to decide how to best utilize the land but the land will matter in this game.
As is the case in game programming, my first performance roadblock that is really hurting the Alpha is the pathfinding. It uses A* and it is slow once you get to 40+ square length paths. By slow I mean you can see it takes on the order of 100s of ms for just a few units.
That's bad.
So I went ahead and added Jump Point Search, JPS, but interestingly it made my pathfinding EVEN SLOWER! The issue is that JPS is only superior to super vanilla blind implementation of A* without even, I guess, a heap to store the open list?
Jump Point Pain
Okay, JPS isn't just awesome by blindly implementing the algorithm as pointed out by Harabor (here's the white paper). But it does add value, if we can figure out what is slowing everything down then we can get what it promises: less nodes to check in the open list which is an O(logn) insert.
First, why is A* faster than A* + vanilla JPS? The issue comes down to how the open list is processed. A* with a simple heuristic ( c^2 = a^2 + b^2 ) gives us a very accurate way of determining the next path to analyze without over-estimation. Additionally, the modified A* in Cultura "prefers" to check paths of longer length between two equal cost (known + estimated cost) paths. This means it will traverse down something that is likely to hit the goal node first and end the search. In practice, this means racing down the correct path almost immediately and finding the goal node. So the costs are a bunch of O(logn) inserts and O(1) pops to get the head.
This is quick but the inserts eventually slow down the pathfinding to a very mediocre speed by even a 40-length path.
Thus begins our quest to optimize the shit out of pathfinding.
Cost Estimation Heuristic
The first and simplest optimization was to improve the cost estimation. Originally it was using the "squared" straight line distance to avoid performing a square root. This avoids the computationally expensive square root in the hopes that it doesn't damage performance.
Unfortunately, that just wasn't true. The more accurate straight line distance versus the square straight line distance was pretty much a different in runtime complexity on path lengths over a 10-step length. This was due to the poor "next node" selection in the A* open list. Doing the full calculation allowed A* to correctly choose the next node without trouble and thus be nearly linear in all typical use cases in Cultura.
These days you can use really awesome square root calculators that make it painless. Here are two things: the ole quick square root popularized by Carmack and the much newer asm_sqrt instruction. My box is a quad-core 3.6 Ghz i8 processor for reference.
Just so you know, here's fast inverse square root:
float CJumpPointSearch::Q_rsqrt( float number )
{
long i;
float x2, y;
const float threehalfs = 1.5F;
x2 = number * 0.5F;
y = number;
i = * ( long * ) &y; // evil floating point bit level hacking
i = 0x5f3759df - ( i >> 1 ); // what the fuck?
y = * ( float * ) &i;
y = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration
// y = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, this can be removed
return y;
}
Method
Time
Quick Square Root
~25 000 000/s
asm_sqrt
~30 000 000/s
I can do thirty million sqrts a second. Or I can choose the wrong node eighty times and spend countless milliseconds hitting the A* open list. HMM!
JPS: Straight Line Jumps
A straight line is pretty simple. The JPS algorithm basically says keep going forward unless there are obstructions. Then you stop. Seems simple right? Well actually there's a lot of checks per square you need to do before you "jump" to the next square. Is the next square an obstruction or within the map? Is the next square the goal node? Are there any "forced neighbours"? Okay, NOW you jump. The number of checks is very significant.
That's not the worst part though. An unstated problem in JPS is that the jumping doesn't stop.
It doesn't look so bad here. We checked seven squares and then determined that this has no jump point successors. Therefore nothing gets added to the A* open list. Fantastic right? Except that in non-vanilla A* with a reasonable heuristic, I would have never checked all but one of those nodes. So what would have been the cost? Nearly nothing. But, with vanilla JPS, I've run through a "jump" check for all seven nodes. And it gets worse with map size. Cultura has very large maps but even something like a 90x90 test map, I'm nearly running 60-square checks for every straight line jump.
These checks can't be skiped. In order to preserve correctness we must do every square. However, you may not need to perform a full jump.
JPS: Diagonal Line Jumps
In JPS, a diagonal line jump is the most frequent kind of jump you want to do because very rarely do you have a straight path to your goal node. However, the JPS algorithm does an extra step to ensure correctness/optimality for diagonal jumps. Every square you jump forward you must also check the straight line jumps that come out of it.
These straight line jumps have all the performance issues as a normal straight line jump because they're the same thing. And notice they can't be skipped otherwise you might miss an optimal path. So for every square a diagonal jump can go we add two straight line jumps. The number of checks grows very rapidly. For a map such as 90x90, each straight line jump can be 50-60 iterations of the jump function each one consisting of 3-5 checks. Now imagine a reasonable map in Cultura, like a 500x500 map or a very large one like 2500x2500, a straight line jump can be 10000s of checks. So a diagonal line ends up being hundreds of thousands to millions of checks versus just a few in A* with a heap sorted open list. JPS becomes insanely slower.
Jump Point Optimizations
What do?
Order of Operation
Let's consider a few situations:
We could have a goal node accessible through a straight line path. We could have one accessible through a diagonal path. And we could have one accessible by neither.
The first step in JPS is to "prune neighbours" before deciding to figure out the jump point successors. That means we're trying to figure out, from the current node that we just pulled from the A* open list, which directions we should attempt to jump. We can immediately identify that if we're in a straight line path (the x or y value is the same as the current node) then we should see if a straight line jump works. Therefore we should prefer to check the straight line first. Otherwise, let's do the diagonal first because the straight line can't possibly hit the goal node; only a diagonal can. Obstructions can change this but the algorithm already accounts for this.
In practice this means using a deque to store the "pruned neighbours". We push front for the jumps we want to check first, push back to those we want to check second. We are preferring to look at jumps that have a chance of hitting the goal node first.
Of course this is only useful with an early exit. If we find a path that hits the goal node we are using the properties of A* and JPS to exit early from the jumping. We have found a path to the goal. Exit now and let the A* handle whether that is optimal or not. If not? It won't be analyzed again. If it is, we found a path and we can return it immediately. Due to the properties of A*, any other goal path can only at best be of equal length.
Delayed Diagonal Checks
A diagonal path needs to make a straight line check every step of the way. But, if the diagonal path can just simply take you to the goal node (because there were no obstructions), the question is: who gives a shit? The answer is nobody. You got an optimal path, you have an optimal path. Use it!
Rather than make a straight line check every step of the way, as stated in the original vanilla JPS algorithm, just delay those checks only when the diagonal path fails to yield a path.
Overrunning the Goal and A*
When you're using a heap for the A* open list, an insert is O(logn) and popping is O(1). Is that expensive? No! But it is more expensive if you didn't have to do it. JPS is meant to reduce the number of open list checks but that's not useful if the "jump" function takes so ****ing long that the heap inserts and pops were cheaper. What's the answer? Leverage both.
Whenever a jump overruns the goal node, just exit out and return that as a jump point successor. Let the A* algorithm figure out whether it should bother to keep going. The cost is cheap. Imagine a 2500x2500 map. You could do a million checks before realizing this jump is not useful. But A* would have known that far earlier, skipping so many checks that it was much much cheaper to have just simply inserted this into the open list. It's a heap, big deal. It'd have to grow to enormous sizes in order to be a problem.
Have a Path, Use the Path
Whenever we find that we have a path with a goal node, we immediately exit out of finding further jump point successors. The properties of A* will guarantee that we won't use this path if it is not optimal. But we can't tell if it is optimal without going to A*'s algorithm. This avoids the need in JPS to do pointless diagonal or straight line jumps, which again, have a significant cost to them. Inserting a potential goal node into A*'s open list and immediately checking its validity saves significant computation time (a single logn insert versus potentially 1000s of jump checks on various squares).
What's Next
Right now we're running at around 120 solutions for ~60 length paths in a 90x90 map per second. For the pathological case of thousands of units operating at the same time attempting to do pathfinding we would want something around 500-600 solutions per second. We can pursue a few other options: precomputation, caching calculating paths, using greedy whenever possible, reducing function calls and other super-optimization of code (right now the code is very pretty and laid out in OO manner).
I'll be taking a two week break from coding this so that is where I leave the pathfinding state in right now. This is a working real world example of using A* and JPS. I'll likely post up the code (as useful as that may be for people making games with completely different data structures, passability rules and so on), when I'm at the efficiency I'd like to be at for the pathfinder.
