RimWorld Technology - Region System
Вставка
- Опубліковано 31 тра 2014
- My game design book: www.amazon.com/gp/product/1449...
Twitter: / tynansylvester
RimWorld Alpha 4: • RimWorld Alpha 4 - Gia...
The game: rimworldgame.com
My blog: tynansylvester.com - Ігри
This was absolutely brilliant. Any chance you could do more like this? For developers this sort of thing is gold dust.
You made one of the best games ever made. Unbelievable how much detail this game has, and how much fun it is.
25:55 Very cool, I would have never thought of that. It seems to be better than simply asking for the position which would be my immediate go to.
Amazing video, thanks for this!
The edge-hashing for the regions is inspired!
I love videos like this! I had heard about cutting the map into regions but never thought that it would solve that many problems all at once. You clearly demonstrate why AND how to do it, and your debug tools are kick ass! Thanks!
I love these kinds of elegant solutions to problems. These sorts of things go a long way toward making a game feel rock solid. Thanks for sharing!
From another programmer to you about the region system. Have you allowed regions to contain other regions for scalability moving forward? This might not be necessary depending on how large maps get (the scope of the game comes into question) to in the future, but allowing that might get you even more bang for your dollar. My point being that eventually you maybe iterating over just as many hashes to get to the points you want as you did cells before. Just think regions of regions and you can easily get a tile based system that can easily be extendable to larger and larger maps... such as continents and the like. All I could think of through the entire video was when was he going to mention quad trees or R-Trees.
Just thoughts (which you may have already had), nothing you need to implement. :D And keep up the good work! This is by far one of the more successful projects I have supported from the beginning.
A hierarchical solution would indeed scale even further, but it would be very, very complex and difficult to create. As a rule I don't make more complex solutions than are necessary. And right now, such an advanced system would be pointless, since the next bottleneck in the system which prevents larger maps is related to ground/world display and storage, not path analysis. And, of course, I don't think there's much value in maps over 400 large for this game because it's a building game about a handful of people, not a traveling game.
Tynan Sylvester I whole heartily agree with everything you said and I even alluded to it in my comment about the scope of the game gets called into question. My point was not that I thought you should implement it at this juncture but whether or not you allowed yourself the capability to do it in the future with much less refactoring after you solved the other bottlenecks. Simple is definitely the way to go, but allowing yourself the ability to expand in the future without reworking everything is a desirable goal as well. It is a fine line we walk in software development.
And to my point I don't know how deep into technology you want to go or which technologies you would want to select to add in the future updates. Technologies usually cost more resources and thus the more tiers you add the more resources need to be obtained for those tiers. With this in mind for the most part resources on the map are finite and the simplest way to increase resources is to increase the size of the map. I could definitely see colonists building vehicles (muffalo/gas/nuclear/etc powered) that allow them to move goods from distant locations on a map back to a base. Or allowing colonists to raid distant villages just as they have been raided. All things I could see a user base desiring down the road that could simply require more space on the game map. Now with all that being said I don't want you to compromise your vision of the game either, as that leads to sub par game, these are just my thoughts to possibly improve the game.
And to conclude, I really admire the quality of a kickstarter experience you have given your backers (including me). The way you have interacted with the community without compromising your vision of the game is something game devs should aspire to. Phenomenal job so far!
@@tynansylvester "Not a travelling game". Lol, how things change. XD
PS, sorry, it's just I love the Alpha/Beta/release differences in all games. It gets silly how things change.
Thank you for explaining how you go about troubleshooting things like this. Makes us all have a better appreciation of how hard you work to make your games work well for us :)
The reachability system would have scaled just fine, if: all newly dug out cells get the same region as the cell where the person is digging from, without recalculating anything. This makes tunneling quick. If the new cell has a non-solid cell adjacent which is of a different region number of this cell is different from the cell the person is on, then flood fill this new region with the number of the region the person is in.
As an added optimisation, you could have a mapping of region number to cell count, so that you keep a count of how many cells are in each region (which is updated as new cells are dug out or walls are built). Then instead of floodfilling the old region number into the new region, you instead check the cell counts of both regions and flood fill the larger regions number into the smaller region. (and if they have equal cell count you can just flood fill the old into the new)
You're right, I could have optimized it more. However, note that it still couldn't handle problems with different pawns being able to pass different barriers.
Tynan Sylvester Oh, I wasn't suggesting that your current way doesn't have many other advantages - it clearly does and sounds like a great approach! I only wanted to point out that there were options available to optimise the old approach.
Very interesting! I would love to hear more talks like this from you
I know this is an old video, but I wanted to point out that a bidirectional search is much better than a-star at determining reachability.
Thanks for posting this! I've thoroughly enjoyed the game and as a (non-game) developer it's nice to see how this stuff works under the hood.
I love these behind the scenes things.
I did enjoy this highly technical talk. Also I love the hashing solution for neighbor regions. I hope you buy see bigger map support with the savings.
So fun and educating, I wish more people did stuff like this :)
Great talk about common path finding problems!
* Macro-optimization: Algorithm + Data driven
* Micro-optimization: Bit-twiddling
Examples:
* RadixSort O(n) over Bubble Sort O(n^2)
* Javascript: function FloatToInt( n ) { return (n || 0); }
Hey Tynan! Amazing work! I love the game, and I'd gladly see more of these technical insight videos. I really like your solutions.
I'm no expert, but have a question/concept I'd like to ask you about.
Would it help short-range path-finding if every character would have a personal region centered around them, and first look in that region, and if it has no match it'd go for the map-region system? Maybe it'd help finding close items (1-10 tiles)?
Of course this might be more work than worth, and cost a lot of performance, I'm just curious how (if even) it would work out.
Best wishes - A fan :D (no, not an electric one)
Thank you Tynan, this video was awesome, is the core of the pathfinding still mostly the same as in current rimworld builds?
I wonder how godly the performances could be if each path calculation were done asynchronously with the current system
Nice! Hierarchical path finding is interesting, I haven't actually read any papers on it yet, I'd imagine it's usefulness would depend quite a bit on scale and the amount of levels.
In the end it's not all that complex, with a few exceptions, but I've already seen quite a few game devs struggling with this. I think this video makes for a good resource on the subject, at least on a conceptual level. I quite enjoy messing around with data structures and algorithms myself but I find it difficult to properly explain how they work. I think you've done a good job at it.
In any case, thanks for sharing!
My pleasure! Funny thing is that I don't even do HPF at all. I only use the regions for object finding, reachability, room annotation, and so on.
Really interesting solutions there. Now to try and implement them in my engine :)
Thanks!
Hi Tynan! Very interesting lecture you pulled off here =) tyvm
Could i ask though, as I am wondering about something;
Have you thought about making like a check to merge these , when they become small enough? Or are the regions completely dependent on the neighbour because of the X, Y & dir. coords in the hash? Just curious, as to how to solve when a guy finds out he wants to i.e build 10k doors in a row, or zigzag with a wall/cave (and unluckily zigzag between the edge of 2 regions), etc..
Hello,
Very nice and interesting video!
I have one question. I may have misunderstood something, though.
When your pawn searches for something, it will first check the local region, and then if it does not find it there, it will search adjacent regions, and so on.
And if I got it right, all regions are absolute (ie they are not centered on the pawn, else it would be way more complicated). What if the pawn is at the limit of his local region, there is an instance of the item he's looking for at the other edge of the region, and another instance of the item on the cell right next to his but on the neighbouring region? Obviously, the next item will be the one in the next region, not his local one.
Love your game. Keep improving it like this and we'll keep playing it. :-)
Awesome. I love the hashed lookup method. I was thinking the whole time that you ought to use a database for those datastructures and searches...until you mentioned how you solved it. Kudos. :)
I appreciate this kind of video :D
I would very much like to see more videos like this. Keep up the good work.
You sir are a genius. This was always something that irritated me about the game, would never have thought of this solution though!
no one ever talks about this shit, thank you Tynan, this helped me a lot
Thanks Tynan! This was very interesting.
the cool thing is that this upscales, so you can do it on very very large regions and then check down into smaller regions.
I know this might not be possible, but i really want to have "infinite" maps as in Factorio. That would just be the best, and open the possibility for different biomes to be found like deserts and arctic areas and jungles, as well as coming across pre-built outposts with your little expedition. While you still can scroll back (or presumably hotkey to a saved viewpoint) to manage your own base while your guys are walking.
Thank you very much for sharing with the community!
I am currently struggling with updating regions.
When an object is being placed or removed, I am recalculating the whole chunk.
This includes removing existing regions, clearing its neighbours references, then floodfilling the whole chunk again, finding edges for each region and setting neighbour connections.
Is there a better way to do it?
It seems like the region system for determining nearest-X will still give the wrong answers - you've moved the failure case from obstacles to region edges. If a person is at one corner of a region, looking for a rock, and there's a rock one unit away but in the next region, and another rock in the opposite corner of the person's region, they'll choose the latter.
I imagine it will, technically, but because they're so localized it's kind of irrelevant, even in extreme cases it's only like a couple dozen cells walk
You're right. This isn't hard to fix, though (it could just search a few extra regions). I haven't fixed it yet but I will if it becomes a problem in practice. The old system had no easy fix; at least the region graph makes these problems solvable.
I am trying my best to make a situation where the behavior you described affects gameplay.
The one case I get that is common is when I have food production near my cafe, and a stockpile for food near it.
If the stockpile is in a closer region, but food on the ground left over from production is clearly closer in an adjacent region, they of course ignore the food on the ground and path to the nearest region.
So they walk an average of 6-8 extra spaces. Every other case is rare or has no impact.
spoonikle You're right, that would be annoying. Especially if they walk over a whole stockpile to get a bit of food. I'll likely end up implementing this.
is it expensive to create an ad-hoc region around an entity (it being center) upon it performing a search? this region 'overlapping' with the pre-defined grid and being checked first should solve the strange behaviours. it also feels like this would be what brains do. create an 'immediately reachable area wherever you currently are' and then expanding by predefined areas if the local search fails?
So what do you do with common regions in the middle of the desert say that have exactly the same number of hashes? Like empty regions with nothing in it. How does the program distinguish between those regions?
awesome, aspiring programmers and game designers should watch
Would an internally generated and remembered waypoint list for each moving entity help or hinder?
This engine is pure gold
Really nice video! I've learned some stuff from it.
One question:
why does the regions store the hashes of their borders and not just the reference to their neigbour regions? wouldnt this be alot easier?
sorry if this is a stupid question ^^
They store references to the "link" at the border, which itself has a reference to both the regions participating in it. The reason they don't store a reference to the neighboring region is that they may be cut off from that region or that region might be rendered invalid and they wouldn't know. Certainly there are other ways to connect the regions besides matching global hashes of their edge-spans, but I thought it was the most elegant solution.
Great information, that was very interesting.
Wouldn't the region system bias paths toward objects in the same region? For example say you had human1 standing near the edge of the region and object1 was 3 spaces away in a different region but object2 was 5 spaces away but in the same region. Wouldn't human1 go to object2 because it stops after searching the region it's in?
The only way I can think to fix it is to check the region the character is in as well as the 3 closest regions to the character. So if the character is near the top right corner of the region then that region gets searched as well as the region above, the region to the right, and the region to the top right.
Some good info, thank you.
Very interesting video, thanks for posting :)
I'm curious, do you find grazing type creatures tend to clump together and graze until a region is entirely empty before wandering to another region and repeating? Or do you have something in place to allow them to consider a nearby piece of food in a neighbour to be preferable to a piece of food at the other end of their current region?
Oh nevermind, I see you've already answered this question :)
Fascinating stuff, I hope to see more technical videos in the future
Ah, you're following this project too, huh?
This was interesting, cheers!
Yahh path finding is fun when it works .... seeing the units going where they suppose to go without getting stuck on everything, or taking a tour around the whole map, or miss a node and go in a staighht line till it hit the edge of the map or crush cause it attempt to leave the map edge. in short many things can go wrong with it.
This was great. I do have a question what happens if item/person is in a regen and the other item is on the other side of a regen but the item is in the next regen over but next tile. With this it would go to the farther item/person because they are in the same regen but not to the one next to them. Or did I miss something? Again this video was great.
As I understand it, it would choose the item in the same region, even if it is further away if we consider the navigation cost. You could avoid this by checking not only your region for the best item, but each neighboring region as well, but most likely you will always have edge cases where it falls apart, as this system seems to rely on the assumption that items in my region are cheaper and better candidates than items in other regions, which is obviously not always correct.
Thank you so much for this. Although i'm not a programmer or game creature i was able to fully understand this video and find it extremely interesting. i always have in back of my mind how i think a game probably works. but without real programming knowledge and game creation experience its all guess work. Having it explained well enough for me to understand is extremely cool and i appreciate you taking time to do this. This also helps us who aren't experts but have little understanding of game concepts to more appreciate what you guys are doing. So many times i see people complain about pace of game development and i believe its due to devs not fully explaining what they are doing. You could have not mentioned any of this but fact that you pointed out half your time with this update has been on this improvement and not just the ones we notice in-game is awesome and prevents people from getting upset that you spent so much time on just half features you actually worked on because we are unaware!
Tynan, i think that maybe in a further update, u should do a "multiplayer" option, where u can play in a 2-4 player sandbox with ur friends, and build a colony each one in the map, and they can be allies, or attack the others colonies.
Thanks, this is very interesting! I have lots of questions now.
Why would you recalculate the entire map every time you placed/removed a wall? (well, I guess, other than "I hadn't bothered optimizing this at all because I knew I was going to overhaul it") It seems like in a huge percentage of cases, you only need to check very locally to ensure that it's impossible for that block (or space) placement to divide/merge two "areas". And then if locally it does look like it cuts something off/merges things together, you'd only have to check whether those two areas are different/the same.
Why hash instead of using regular pointers/references (to an intermediate "link" object I guess)? Is it too messy when you have to recalculate? why contiguous lines for links instead of having a "link" be a set of all tiles between two given regions? (I guess for easier hashing?)
For hierarchical pathing and other stuff, have you considered making a "tree" of various sizes of sub-regions, like a quadtree-like thing? or is that overkill? Seems like the semi-arbitrary constant region size just reduces the problem by a constant (though large!) factor.
I think that letting the "nearest" object be suboptimal in some cases (like standing near the edge of the region) actually makes the behavior a tiny bit more human. Human heuristics are never perfect, either. (well, these guys can still sniff you the nearest food even when it's across the map, so not *too* terribly human I guess)
There are cases where multiple blocks change in the same frame, which makes the optimization problem somewhat harder than your examples. It is still solvable, though, but I didn't want to spend the effort on an ultimately unsustainable system.
It does use pointers to a "link" object. The question is: how do you find that link object, how does the other region find it, and how do you make sure it's the same one regardless of the order in which these events occur? The hash set is a set of all the links which currently have at least one participant (of course, when the region remake algorithm is not running all links will either have 2 participants or be garbage - 1 participant links is an intermediate state).
Quadtree is possible, but overkill.
And about the suboptimality, I agree in general.
Tynan Sylvester Cool, thank you!
I guess I was imagining some kind of doubly-linked-graph data structure but I see how that still needs the hash table to implement it in a sane way, especially for the updates.
Awesome video. Thank you so much. But doesn't your hashing method restrict your map size to 255x255?
No, it uses a few more bytes so I believe it handles coordinates up to 1023 at least. The 8-bytes-per-component thing was just an example. The truth is something like 11-11-5-1
Great video!
Somewhere on the forums, about 2 years ago you were going to make a new, more detailed video. Many people have a great interest and many questions about the system of the region.
How running a script at the regional level? The region may have a different size, so
how do you determine the weight of the region? or simply choose the path with the least number of crossings regions?
I downloaded the latest version (a14).
I select view setting-> Draw Paths.
judging by the picture, regions NOt used in the patfinding???
0:09 oh so the mapping is done once for the entire map and then it only updates in a smaller square that something changed in...
Simple and effective, nice!
This is a really interesting way to prevent A* searching it's way into inaccessible rooms.
You mentioned wanting to use larger levels in the future, but performance wise it seems that Unity can handle just about 300x300 tiles on an average gaming pc. How did you or are going to make Unity handle more objects/tiles?
I'm wondering because I've heard creating and destroying objects when they're in or outside the screenregion is too slow.
I can learn a lot from video's like this, please consider making more :)
I don't use Unity objects at all, actually. The whole engine uses my own object and time framework. Unity isn't designed for 2d tile-based games with 100,000+ live objects.
that's because A*star isn't the end all be all of pathfinding. It comes down to how you manage the points/tiles/objects to check first, then use A*star. Which is the obvious logical come across for someone thinking of how to generate the quickest path.
I did A*star unknowingly doing A*star, and I still don't know why people think it's so awesome...it's just simple coordinate maths and logic tied together..
I assume there are at least some GameObjects that actually do the rendering? Ones that traverse your object framework and build meshes or something that unity renders?
This is really cool! Very nice explanation of your codebase.
For trying to find an object type (food) in a region, it seems like it'd be nice to also first check the region to see if the size of the object type list is greater than 0 (i.e. is there food in this region).
That way you won't waste time searching each cell in each region if there's no food anywhere (i.e. if the character's in the middle of a giant desert).
Good call, and yes the system does this.
Yo, I thought I commented on a video of Rimworld years ago, and I was right! I bought the game a few months back before it was on Steam. It's a lot of fun, and development really does keep improving the game. Keep it up, man!
I was working on a similar game (programmatically) and came up with a very similar solution to your region system. I think I ended up making it a bit faster, though. Sort of. Depends on how you look it up, but I felt pretty clever. Each resource had its coordinates in integers, both regional and subregional. I would then subtract each coordinate of the searching actor from each coordinate and get the absolute difference at the region level, then starting from the bottom of those, find the closest absolute position in each region and pathfind my way to it. If it was accessible, and not suspiciously expensive given the regional coordinates, I went for it. It didn't produce optimal pathfinding solutions under certain circumstances, but I found that it worked pretty well. I had a 3d map that was around 200x200x200 with dozens of actors and they found everything just fine. I think I chunked the regions into 8x8x8 or 16x16x16 cubes, I can't remember.
Either way, it's a fun problem to solve. The nifty thing about it is that you can keep at it for a day or three and still come up with somewhat more optimal solutions without feeling like you're getting no return on your effort.
I would then subtract each coordinate of the searching actor from each coordinate (of the resource)
Also worth noting that the resources each having their coordinates were obviously grouped by resource. So, I'd have grass_regional_coords and grass_local_coords, for example.
For your algorithm finding the closest path, did you account for if the closest object (realistically) to your player goes diagonally through two regions. That probably made no sense so I will try again. Lets say your player and the object are near the corners of diagonally adjacent regions and there is another object that is in an edge-adjacent region. If the object that is in the diagonally-adjacent region is technically closer, which would the player go to?
Hi, how did you solve the following problems:
1) Suppose we stand near the edge of our region looking for food. There is one food right next to us in the neighboring region and another food at the far end of our region. As I understand, the algorithm will result in getting the one in our region, despite it being farther away from us. (Edit: found the answer in the comments)
2) Suppose we stand near the edge of our empty region looking for food. The food is 17 cells to the east, so there is another empty region between us between us and the food. Now suppose fill the region with doors. Each door is a separate region, so it will create 16 tiny regions between us and the food. The distance did not change (suppose we can pass through doors as fast as through empty space), but the pathfinder would rather pick neighboring regions even if they contain a long maze.
I am thinking of a way to abuse it for base defense purposes.
I have to say that i really like the region system, while quite tricky it definitely is much better solution than global lists (those really wont scale with larger or infinite maps). Also, if you haven't already, you should add jump point search algo on top of a*, it really makes great improvement in terms of pathfindining performance..
JPS can't handle variable path costs so it won't work in RimWorld (where different ground types, crawling over items and such all have different path costs).
Tynan Sylvester Oh yes, haven't thought of that. It came to my mind that JPS could create rough estimate of the path which could be adjusted using plain a* while actor is already on its way, through that would probably be overly complex solution with very little gain..
Hey I know that this isn't a place to suggest things but talking about doors could you make doors that prisoners can get through?
Might want to add the speed of opening a door vs going around the door into the equation...
Very nice! I wish I had the source code to all of this to see how it work :P
What if; you mined out an entire cavern on one edge of the map, but added a door on the connections to the outside, built walls around the cavern so the cavern part could take over their regions and continued doing this till the other edge of the map. This would override the "outside" world and consider everything a cave interior, right?
Brilliant
Genius!
i know nothing of technical stuff but this does a great job at explaining it thanks
Do you reckon Dwarf Fortress does something like this or has something like this implemented? I always get FPS lag when I visit the circus. Clowns trying to path to impossible places :P
Awsome stuff. It'd be great if there were time to do more videos like this. But I get actually coding is a better use of time =)
as someone who's planning to go into this business, I find this extremely interesting!!
one question though, concerning pathfinding:
take the image at 14:08
add another colonist at the bottom of the region victor (the guy looking for a talking partner) is in.
Victor will go to that one, although he'd be a few steps further than the other person right ?
in this specific case I doubt it'd make much of a difference, but if there are more serious cases, is there a way you deal with that ?
You are correct that Victor would incorrectly prefer anyone in his region over someone closer but outside his region. There is a rather obvious fix for this (just search some extra regions after you find someone, basically), but this failure hasn't been important enough for me to bother implementing it yet.
Tynan Sylvester
I was going to ask a similar thing, but it regarding doors specifically.
Ah cool, was wondering the same most of the video. But I guess as the regions aren't very big and obstacles are completely handled, at most you will only have someone walking (region_length/height - 1) out of there way to get to something.
I was wondering: "Is this a new version? It looks a bit different."
No, it is 5 years old :D
Won't the regions system create localized behavior shifts, though? Like muffalo only grazing in one region for grass, because they'll check it first, even if there's closer cells outside the region?
Hashing the links is a cool idea.
You are correct. They will walk across their local region to get some grass even if a neighbor region has some closer. There is an obvious way to fix this, but I haven't done it yet because it's just not that important.
You explain stuffz really well just sayin...
Thank you Tynan for sharing these inside concepts and ideas. As a newbie game developer, i learnt a lot from this video.
Honestly, I was hesitating whether purchase RimWorld or not although i really love it(30 bucks is little bit too much for me ":(
However, i actually bought it right away after watching this video. :D
Great game!
So what happens if one guy wanted to have a nice chat and started looking for someone, but the closest person as the crow flies is 4 blocks away but it just so happens that those 4 spaces has a region border. Meanwhile another guy is 13 spaces away but is on the other end of the same region? Will the guy looking for a chat realize that the other person 4 spaces away is closer or will he be limited by the region system and go to talk to the person 13 spaces away? It seems like a really good cure for the system but it also widens the scope a bit and leaves it open to some quirks.
Never mind. I should read the comments before making my own. Derp.
As to just want to point out that when showing the co-ordinates for each tile there where 3... So, Are we going to see an extra Z level like dwarf fortress? (open your eyes america)
Wouldn't hexagonal regions be more efficient?
Right now you have at least 5 region checks before you begin to check regions 7 9 1 3 (Numpad layout).
So my guess is that you are looking at the close by region in an order that looks like this? 1-9.
647
213
859
With a hexognal system you'd only need to check 7 regions.
Maybe, but this would be an extremely difficult micro-optimization with significant maintenance/complexity overhead for a microscopic potential benefit. My goal isn't ever to make the most perfect system possible. It's to solve the present problem and move on.
Cool! But... this still means that if I wipe all plantlife from the map, the starving animals will still cripple the performance :( I'm starting to think that Tynan opposes large-scale animal cruelty simulation. Sigh. I suppose I could try and mod the muffalos to be berserk 100% of the time.
If there are very few plants (nothing found within 30 regions), the system will fall back on global search and only check a relatively small list that are left over. You're right that the system isn't ultimate and perfect for all map sizes and circumstances (yet).
Tynan Sylvester
It's all good. Personally I'm more than pleased with all the progress that's happening. May you earn millions.
Tynan Sylvester It shouldn't be necessary for a group of animals to search the whole map in futility. Only within a limited range, otherwise they should wander around. Animals are likely to hang around places they know have food. When the food runs out, they explore, typically by sight or smell.
'Zombie Virus Active'? Welp.
yo tynan check facebook bro i want to do an interview
yo lo queria en spanish plis😭😭😭😭