Jump to content

Two stage pathing


Recommended Posts

Pathing is a gigantic CPU drain in the game, so if there are places to save CPU cycles then pathing is an excellent place to start. Currently the pathing system does an enormous amount of redundant work. One dupe works out a path across the map, then another dupe has to discover their own path from scratch, then another and another and another. Why do the same job dozens of times? By taking a two stage approach the heavy lifting can be done once, then boiled down into far simpler problems for the dupes.

The key mechanic to this idea is to use ROOMs. Rooms have many advantages such as:

- They are the defacto access points between rooms

- The game wants and demands that you use them

- They're large and there's a very limited number on the map

Rooms are connected by doors, so doors are excellent connecting "nodes" between rooms. The mechanics are pretty simple. If one dupe can path through a door, then ANY dupe can path through a door(keeping it simple for now). If two rooms are connected across the map, then any intermediate room is ALSO connected. If any dupe is inside any of those rooms, then they have automatic access to all those areas. Dupes no longer have access to 100000 thousand individual tiles on the map, they instead have access to a few dozen ROOMS with stuff inside to do.

Item mechanics are a bit different. If an item can be hauled to a door, then it has access to the node map. If an item can reach a spot inside the room from a door, then it automatically can enter the room from that access point. These facts only have to be discovered once, then they can be freely used as long as the source and destination rooms don't change. An item ends up with  three much smaller tasks to condsider. "Can I leave a room", a simple yes/no. "Can I reach across the rooms", a short pathing check, and "can I reach the target inside the room", another simple yes/no. There's no need to discover these facts more than once!

There are some downsides to the approach. For example if a room is very large or under heavy construction, the macro step becomes extremely taxing. If a large room changes shape, then all the items inside have to reconsider if their pathing is still viable. A different approach may be needed, something as simple as a "do not touch, under construction" sign is the dumbest solution. However for a well organized, completed base with many rooms, the final path checks get to be very fast. Few things change, so few things need to be calculated.

Items may derive additional shortcuts as well. For example if one debris occupies a tile with another item that contains a viable path, it's good. Pathing inside a room may be a simple picture of yes/no dots already solved, so the tiles already know their designations and the items don't even have to worry. If a tile is viable, then a million items can be in that tile and they don't have to check anything because the tile is already solved. I dunno. Get creative.

Link to comment
Share on other sites

I don`t know much about pathing programming but changing the system to be room based sounds complicated. Large overhauls like that are unlikely. But the principle is simple. If a dupe can path to another dupe the other can path to the same places so there is no reason to recalculate the path for the other dupe. Almost no reason. Proximity stuff possibly requires pathing so the dupe does stuff close to him. Again it`s just assumptions so i don`t know if it`s actually doable without removing half of the code.

Link to comment
Share on other sites

Pathing takes a lot of resources. Ever since i started to have single ( yep single) path to get any destination game works much more smooth than before. It takes some effort cause you need to find all rouge paths but when its done it is game changer on later stages. Currently cycle 1200 running all the time x3 speed with no lags ( apart of new day which stuck for 2-3 seconds)

Link to comment
Share on other sites

Reducing pathfinding grid to a graph of waypoints ("navmesh") is a pretty well researched technique for optimizing pathfinding. It's not always easy to design, but it's true and tried.

ONI is on a grid, which makes it much easier compared to more freeform (ie. float valued coords) systems.

Though using "rooms" as such would be rather specific and thus probably not the best way to go around it. Rather, waypoints are placed where "decisions matter". A long corridor with many doors can be only traversed in one way, so it would only get two waypoints, for example.

Link to comment
Share on other sites

Though using "rooms" as such would be rather specific and thus probably not the best way to go around it. 

Not really. A room is a self contained system that clearly separates areas. The game design already establishes rooms as essential objects in a base thanks to their bonuses and essential features. Since they exist, they can be exploited as navigational aids. If a room can be pathed, then the particulars of that path don't really matter. Simply knowing that the path exists will cut out all the redundant work of trying to find a viable path every single time a dupe wants to find a thing. 

Rooms are separated by doors. Doors are essential nav points because they can be open, locked or have dupe access permissions. If a dupe is going somewhere they must go through a sequence of doors to get there. Once a connection between doors is established, the intermediate tiles once again aren't very important. Checking if an object is accessible through 10 doors and the last few steps is much faster than scouring the entire map for a viable path. A giant maze of doors would present a large navigation map, however, it's not going to be any larger than the default navigation process of checking every single tile on the map. 

Why should a dupe have to KNOW the exact walking path to every single task they can potentially do, at every moment in time? They can only perform one errand at a time, and each task takes some time to process. All that matters for choosing an errand is knowing "can I actually DO this errand?". That type of check does not need a full scouring of the world map. It can be boiled down into far simpler, and far FASTER generalizations. Once they choose the errand at the macro level, they can worry about the details.

Link to comment
Share on other sites

Here is a link to a video by the programmer of the game RimWorld about how he implemented pathfinding in RimWorld.

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

Basically, he divided the map into 12x12 tile regions and the agents use these regions for pathfinding instead of individual tiles. This is much better for performance.

This is also similar to the suggestion of using rooms for pathfinding, but doesn't have the disadvantage that rooms can have very different sizes.

Link to comment
Share on other sites

On 8/29/2019 at 5:38 PM, bobucles said:

Not really.

Yes really.

A room only encloses a player-designated area, explicitly "claimed" and chunked by the player. This means that all of those would not be covered: long ladders (very important), space, caves.

Many rooms would be huge, which could easily undo the performance gains from room-specific waypoints, unless the players were informed by the game on this room pathing hack and traded travel efficiency for CPU cycles by cutting the ladders up into door-enclosed sectors.

It might be enough, but it's still only a hack, definitely and unarguably inferior to a proper navmesh generation algorithm. Which is also much more likely to be well documented and thus easier to implement correctly, without running into tons of edge cases. Why reinvent the wheel when the real deal is obviously superior?

Link to comment
Share on other sites

Archived

This topic is now archived and is closed to further replies.

Please be aware that the content of this thread may be outdated and no longer applicable.

×
×
  • Create New...