Friday Facts #117 - Path Finder Optimisation I

[SilverWarior]

sometimes biters on the sides of a group will sometimes branch off from charging a direction to go somewhere else or attack something else. I'd really like to understand how they work, so don't be afraid to post an essay about it, this stuff really interests me and I love learning

The reason why some tiers may branch from group and start attacking something else is that when biters are aggravated and moving they are constantly scanning their surroundings for potential targets. And if they found such target in their vicinity they abandon previous destination as set that target as their current destination.
Without this mechanism in game biters would go crossing your entire base before reaching certain the area from where the pollution that aggravated them is spreading from.

[vanatteveldt]

(1) You can allow biters to walk through other biters and trees as long as it is offscreen (and when the screen comes near the biter, simply teleport the double biter to a new location with a confused look on its face)

(2) I like the gradient/pheromones idea. Caching paths should be pretty cheap as it is simply one extra number for each tile with the "elevation". The cool thing is that you don't actually need to long-range pathfind for the biters since they are not supposed to follow an optimal path (being animals and all). If the gradient is something like pollution plus earlier biter trails the biters can "learn" the path to your base and stick to their existing paths, and only activate (local) pathfinding once they see a target. This would even allow for technology like pheromone detection (to see which part of the base to defend most , although that is generally clear by inspecting wall damage ) and especially pheromone planting to lure biters into a trap.

[Brambor]

I like the technology research as well! Cost could be something like something and 10 purple (or more) per cycle, as you need to investigate aliens. That would give you the ability to construct tool for detecting such a thing, the tool could be building with similar behaving as radar, only it will run on much lower space and, as radar, it will finish it's searching in quite a long time . What do you say, developers? Should we make a new topic about this in the ideas section?
There could be even a thing (but you would probably not agree) that would allow you to clean the place from this pheromone and make a different trail, so you can lead the bitters towards your defensive outposts and leave your main base safe

[SilverWarior]

I'm wondering why developers are avoiding of implementing a heuristic path finding algorithm.
Heuristic path finding algorithms excel in finding long paths especially on maps with large unreachable areas (big lakes or walled in areas) or room based maps (using walls and gates you can reach this in Factorio).

So how heuristic path finding works?
Unlike normal path finding algorithms heuristic path finding algorithm perceive the map from two or more different levels.

On lowest level the map is perceived in the same was as it is done by standard path finding algorithms (standard grid).

On higher level maps is perceived differently. Here several of grid cells from the lowest level are grouped into sectors. These sectors then have connection points to other nearby sectors. These connections can then tell you if you are even able to reach nearby sector fro the current one and what is the estimated path cost. While sectors are usually square shaped where squares have same dimensions it is not necessary to be so. You can have customs shaped sectors (most commonly used for treating a single room as a sector) or even have different sized sectors.

So you always start preforming path finding at highest most simplified level and generate simplified path that leads from origin to destination sector. Once that is done you preform path finding algorithm on lower level but you limit your path finding to only search within those sectors through which the higher level path goes. This reduce the number of nodes that need to be scanned by lower level path finding algorithm.

And the best thing is that you can have as many heuristic levels as you need. So you case of large and complex maps you can reduce the number of scanned nodes for the lowest level to just a fraction of those that would be scanned if only using path finding on lower level (classical approach).
Another great advantage of heuristic path finding algorithms is that you can actually use different base path finding algorithms at different level (which serves best for that heuristic level). This can improve the overall performance even further.
And if you also upgrade your heuristic path finding algorithm with caching ability for different heuristic levels you can speed up the process even further.

If you want to learn more about heuristic path finding algorithm you can check the link bellow:
Layman explanation how another game you probably know (Banished) is using heuristic path finding algorithm: http://www.shiningrocksoftware.com/2013 ... -problems/

[ske]

Considering the path finding optimization.

How about making a gradient map that would guide the biters. When they attack, they always go to the same target, the player base, and that does not move. You could grow a gradient from players structures outwards, for a precise solution. Or simply from the centers of the sectors (map chunks) that contain player structures and continue with normal path find below certain distance.

This cost memory but saves cpu cycles. You don't even need to update the gradient immediately when player builds something, let the update run in background and bitters get close enough using the old data then again switch to normal path find.

I think this idea is worth following a bit more, cause all the paths need also memory.

And if you think this to the end a gradient map can also be seen as a "smell" or a cloud of pheromones. See https://forums.factorio.com/forum/vie ... f=6&t=3440

The natives can learn to avoid or focus on things, just by changing the gradient.

Yes, this makes so much sense. The biters cannot do much pathfinding themselves. They don't have infinite sight. They can't plan ahead too far. They are stupid little critters.

Having simple "smell" overlays with pollution, paths to the base, deaths, and successful attack positions might really help making the attacks seem more real and intelligent. Suddenly the beasts will start running circles around the base probing the defenses a weak link.

[Anoyomouse]

external development (in Python) of the mod portal went silent in the past month

So, is this an open project, i see many people who want to help, mostly with PHP / DB stuff, and already having slight problems with versioning on my warehousing mod, I thought i'd ask if anyone can get involved (i have and extensive python background), so would love to get involved, but i can't volenteer too much of my time (i'd love to offer to take it on, but i know sometimes i don't get much done on my own)

wondering if that has anything to do with www.factoriomods.com as well ^.^

[ILMTitan]

One way to fix the long paths problem is to simply have water absorb more pollution. Right now it can be annoying to have to walk around a big lake to eliminate a problematic biter base. Water absorbing more pollution would help with both that gameplay annoyance and the reverse biter pathing performance issue.

[DaveMcW]

Absorbing extra pollution would make water starts even safer than they are now.

A better solution would be to reflect pollution. Increase the diffusion_ratio to something approaching 100%.

[AssaultRaven]

The risk to factories now is that pathfinding around lakes proves more difficult than expected and we see in the patch notes:

"Gave biters the ability to swim."

[Xerophyte]

Considering the path finding optimization.

How about making a gradient map that would guide the biters. When they attack, they always go to the same target, the player base, and that does not move. You could grow a gradient from players structures outwards, for a precise solution. Or simply from the centers of the sectors (map chunks) that contain player structures and continue with normal path find below certain distance.

This cost memory but saves cpu cycles. You don't even need to update the gradient immediately when player builds something, let the update run in background and bitters get close enough using the old data then again switch to normal path find.

There are pros and cons to gradient caching, which is essentially just storing a permanent solution to the path finding problem for every point on the map. The memory cost isn't necessarily one of them since you will very rarely need a very fine grid: when near the goal then you can use individual paths and not care about the cache and when far away from the goal (or player!) the resolution can be extremely coarse and it's sufficient if the biters run in roughly the right direction. You also don't need much resolution for the gradients so you can in principle settle for a fixed 256-ish directions/node if you want, though in practice you almost certainly want to store distance to goal to make the cache easier to work with (E: essentially, the gradients of the gradient map are the gradients of a signed distance field, so you can just store the signed distance field since it's more useful). With a hierarchical grid, sparse octree or similar then we're still talking something the order of a few hundred kilobytes to store a grid of arbitrary size which shouldn't worry anyone. Since the game already has a path cache it might well work like this, I dunno.

The main problem is dealing with natural obstacles like trees, lakes or biter bases. You don't want to permanently store a fine-grained grid for every forest on the map, so instead you have large, partially passable grid nodes that biters will then need to navigate through on demand. There are a couple of ways for them to do that: let biters run straight through any obstacles in a partially passable node as long as no one sees, use A* or similar to correctly path through at all times, be really goddamn clever about adaptive cache resolution and invalidation, etc. None of these are perfect and finding a good balance is tricky.

I'd say to just try to cheat as much as possible, in the best tradition of games everywhere. Ignore obstacles if no players are nearby. Ignore pollution if the direct path is sufficiently obscured, for some value of sufficiently.

[vaderciya]

The risk to factories now is that pathfinding around lakes proves more difficult than expected and we see in the patch notes:

"Gave biters the ability to swim."

Is anyone else surprised that there aren't more than two " kinds" of biters? We have biters, and spitters. But we don't have flyers, or any leviathan.

[Satis]

To be honest, I don't understand why you would want an mod portal, since you are preparing to go to steam anyway,
so why not just use there workshop system for all the mods, which will make everything easier.
With the workshop you can auto update mods if they are updated by the creator and with some small tweaking, you can sort every mods by types as well.
I can only see the benefit of using the workshop.

If there is another reason to have an mod portal over the workshop, could you try to explain why?

Kind regards
Satis

[goron]

Tynan Sylvester form Rimworld explained some tricks they did for their pathfinding.

https://www.youtube.com/watch?v=RMBQn_sg7DA

[ssilk]

I like how the debug mode in Rim World works.
I also made some research and found this old FFF: https://www.factorio.com/blog/post/fff-36

So the devs know about hierarchical pathfinding.

[MasterBuilder]

To be honest, I don't understand why you would want an mod portal, since you are preparing to go to steam anyway,
so why not just use there workshop system for all the mods, which will make everything easier.
With the workshop you can auto update mods if they are updated by the creator and with some small tweaking, you can sort every mods by types as well.
I can only see the benefit of using the workshop.

If there is another reason to have an mod portal over the workshop, could you try to explain why?

Kind regards
Satis

You can't download mods from the Steam workshop, only subscribe to them. If this is the only way to get mods, then anyone who does not own the game through Steam is screwed.

[Darthlawsuit]

Really humans tend to send out scouts/recon to figure out a path to get to a target. That recon team then relays that information to the army and the army will take a path along the path the recon team found. They might change the attack location when closer to the target but if there is a known path they normally take it.

Biter scouts/recon and caching might work the best. Then sharing a cached route with other biters who are also angry with the player.

[jorgenRe]

The risk to factories now is that pathfinding around lakes proves more difficult than expected and we see in the patch notes:

"Gave biters the ability to swim."

Is anyone else surprised that there aren't more than two " kinds" of biters? We have biters, and spitters. But we don't have flyers, or any leviathan.

PSST: worm that burrows a tunnel for biters to use !
Tiny biters that explode on impact. A reason to build double walls !

[Brambor]

Or walls really, I do not use them since they only add HP, and they increase the size of an object, so bitters aproach walls and damage them but if they were not there they would not reach the turrets. Before critics I want you to think about it.

[vaderciya]

Or walls really, I do not use them since they only add HP, and they increase the size of an object, so bitters aproach walls and damage them but if they were not there they would not reach the turrets. Before critics I want you to think about it.

I completely agree, sometimes walls make things worse

[_Skuzzzy]

external development (in Python) of the mod portal went silent in the past month

So, is this an open project, i see many people who want to help, mostly with PHP / DB stuff, and already having slight problems with versioning on my warehousing mod, I thought i'd ask if anyone can get involved (i have and extensive python background), so would love to get involved, but i can't volenteer too much of my time (i'd love to offer to take it on, but i know sometimes i don't get much done on my own)

wondering if that has anything to do with http://www.factoriomods.com as well ^.^

Seconded, what is the status of a mod portal? Would it be something that the community should get together and create?

I have a fair amount of development experience and would be interested in contributing to the development of something like this.

I am just concerned that if the community starts working on something like this and then the devs come out with an "official" solution, that is a bunch of time wasted.

Also what is the status of factoriomods.com? It looks like they have a great start on the site and started investigating the protocol(some issues I noticed with it), but it has not been updated in 5 months.