Pathfinding in games. How to do it for 30k entities.
Вставка
- Опубліковано 8 кві 2020
- Pathfinding is often a huge component in games and a major bottleneck. This is me rambling about how I've managed to implement one that's really fast. It explains pathfinding casually and a certain algorithm called HPA.
Info about pathfinding: qiao.github.io/PathFinding.js...
HPA: webdocs.cs.ualberta.ca/~kulchi...
I smack my lips a lot. I didn't know I did that, it's really annoying.
The game: songsofsyx.com/
As a dev, not as a direct fan of your game, I would back your kickstarter in an instant if you made regular videos like these. We don't get videos on this genre of games other than the random ones once a year from Tynan(Rimworld). Space haven, starmancer, embark, frostpunk, cities skylines, indie or AAA we don't really get to see under the hood of successful, or even heavily indev projects.
The best thing we had was Desktop Tuesday from Stonehearth, and while I get it takes a lot of time to put something like that together, i'd happily pay for that.
i would second this.
I find this very rewarding and I really wish I could do more, but I still have many years of 14h work days to put into the game itself. Hopefully I will be able to do some more one day, I'd really like to, though I wouldn't want to make it profitable, I think that would ruin it. Thanks for the encouragement!
Seconding this, but also as a fan of the game too. Impressive work, and thank you for documenting your processes and sharing your knowledge.
@@songsofsyxofficial9516 And you say you're not a genius, but you clearly are a strong thinker. The fact that you took this algorithm from a random youtube video of a lecturer talking about it and did an implementation is proof of that.
I think there's a difference between having fast brain processing speed and being a skilled, structured thinker. The former is certainly nice to have, but the latter is what makes it possible to keep moving forward and keep making progress regardless of the problems laid in front of you.
@@human-ft3wk the idea of the genius programmer is both toxic and just straight up a lie. He got to these conclusions through LOTS of iterations, and lots of devs and mathematicians before hi,
Dwarf fortress: we have 10 units and we need i9 100500 CPU-core for pathfinding.
SoS: 6k units and one coffee-machine
but DF is 3D 😏
the non-steam version of DF is only utilizes 1 core.
Pathfinding in DF really isn't the thing slowing stuff down. One of the devs they hired went thru and profiled it, and the problem was actually the visibility /line of sight checks used to inform the AI's behavior. 'Putnam' on the forums wrote about this in "Pathfinding is not a major cause of FPS death" thread, page 12.
It's really fascinating.
@@ultimape Yeah that was interesting. Too many dwarves seeing other dwarves, trying to decide what to do with one another and how they feel about it!
I yelled out loud when I saw the large grid squares layerd on as I instantly understood what you were going to do. Thats so damn smart honestly, makes me wanna try programming again lol
Having a lot of fun with your game, totally hooked. I’m implementing a similar approach with a game I’m working on, this was quite informative. Thanks.
I really like the much simpler pathing solution, of making the player place signposts, that act at path-nodes, and that automatically list nearby addresses as the local neighborhood.
In addition, each door+room is known by all signposts to what signpost it belongs and signposts automatically generate doubly-linked-lists of valid paths between them. (may be s precise or a chain-link of sub-nodes or just a vague vector)
This seems much faster within Data-oriented programming.
I like to think that Themep-park (1994) did this, but i am not sure, surely it is a smoother/optional approach to how Settlers (1993) obviously makes path-node-placement a mandatory core mechanic.
Really enjoyed the video, currently looking into ways of improving performance for path finding in my game so will be sure to give HPA* a try... Looking forward to watching the rest of your videos and trying out your game. All the best
Good video! Very educational for a lower primate such as myself.
I am looking forward to this game! Very ambitious and very neat!
Bonobo is the highest primate, though I have seen some pretty high humans
Just bump into this video
thank you, this is very inspirational
A better implementation might be utilizing R tree, I guess
or create a grid by Voronoi diagram. Which in either case, the weight/travel cost of individual cells (mud etc) is calculated to create that "abstract grid".
Can't wait for the 0.63 to come out.
Great video and really helpful for what I'm building. Could you do a video covering your grid data structure and more information on how you handle online given the size of your game world?
Another path-finding technique you may find helpful (specifically for large-scale battles) is "Continuum Crowds" by Treuille et al.
Please! this is very helpful, I was so proud of my A* algorithm working in my game maker game, now I really need to know how this works. Thanks so much and more would be so helpful!
So what if there's a wall that goes along a side of a chunk, or a 'U'-shape. Can the path finder lead a character to a dead end? The chunk-to-chunk algorithm may find paths between chunks, while a character could cross a chunk border and end up in a 'pocket' / dead end. Surely you don't keep track of every tile-to-tile chunk crossover case. How do you solve this? In other words, you could have a tiny pocket at the edge of the chunk, and a character happens to cross into that chunk just at the pocket opening, he would need to reverse and return to the chunk where he came from, but now his chunk level path finder says he can cross over again.
I should have shown that case. The answer is that if you cut through a chunk, that chunk becomes two different chunks. A chunk can be as small as 1 tile. There are never any dead ends this way. And if you really mess up the map with obstacles, you can indeed render the algo useless and waste a lot of memory. It never happens in practise though. It is still very useful, even though chunks often are divided into 1-4 "sub chunks".
@@songsofsyxofficial9516 Thanks, game looks great. I've been worrying about the same problem, but I will at most have around 1k actors on the map at a time. Here's a great blog post of Factorio's path finding algorithm: factorio.com/blog/post/fff-317
Question, how do you make the characters not all walk single file? It seems like they find slightly different paths every time and that makes it look more natural
Please keep making videos like this! I am a huge fan of Songs of Syx and have scratched my head how you managed to pull off things like
- Pixel art and lighting engine, look fantastic!
- Characters wearing away grass in high traffic areas
- How does it run so smoothly with thousands of characters???
Keep up the great work :)
Thank you! I blame stubbornness. Just keeping at it, there's a optimal solution to everything. It's nice you've noticed the pathing thing. It's actually that each path increments an integer on the tiles it crossed. Then I do the path finding and using the integer as a weight, while slowly decreasing the value each update tick, cooling it down. It kind of works with the right amount of people walking in the same place, can be weird on some occasions.
@@songsofsyxofficial9516 Did you have some sort of dev background before this? That's a brilliantly simple solution, I love it.
@@connorbogunovic1647 Yes, I had half a degree in computer science. I can recommend "computer algorithms" (there aren't that many of them). They are really smart and simple, and I think it's a benefit knowing them if you're to have a chance of using them and coming up with good solution by yourself.
@@songsofsyxofficial9516 Thanks for answering! I'll look that up, thanks for the suggestion! I still think it's incredible you've made this game with only half a degree of experience... the sheer complexity of it is very impressive! Thanks for sharing both this game and your knowledge with the world!
It sounds like you're using a hierarchal system combine with something akin to Floyd-Warshall for your caching? Really cool.
Don't you dare catch covid before finishing this game.
Nah he survived how about you?
Great video explanation of the pathfinder
sir, in one hour i will buy your game on steam. As a beginner programmer I really liked your explanation! Good luck and keep developing this fantastic game!
This video is excellent. I adore developers getting into the details and showing how things are implemented, problems encountered, and the solutions to those problems.
By any chance do you have the UA-cam link for the "HPA" pathfinding that you mentioned?
Please don't stop making these sorts of videos. Very nice content!
thank you. No, don't have it at hand ATM. I have since then pimped up the algorithm to be a total divide and conquer thing, works very well, except for a bug I can't find. Hope to be able to make a video out of it one day.
@@songsofsyxofficial9516 nice! I would love to see an updated video with your new and improved pathfinding 👍 whenever you free up enough to create it. You are doing a fantastic job with the game, and the amount of content you are producing at such an incredible pace speaks for itself.
Did you implement a portal graph on top of the chunks? If yes, than you can approximate the path.
In short, you can calculate a* only to the end of the next chunk of the chunk agent is currently standing on top of. Many RTS games use this tecnique. Extremely improves editability of the terrain. Also saves a lot of resources if the agent does not follow the path until the end.
With your look into Hierarchical Planning A*, what other methods did you look into to make a* faster? Did you look into RSR or other neighbor reduction/ map optimization methods (jump point search? Ant pheromone style optimizations?) What made you land on this one? What tests did you perform to determine if this was the right method to do make A* faster? (if any?)
Anyway I like the way you present, and I like that it promotes your game, thank you for making the video.
I looked into JPS, but found it was pretty useless in my case. My impression is that you only get gains if you have a slow priority queue. You lessen the amount of puts in the queue, but quite often increase the amount of tiles that need to be examined. Regardless, comparatively I find that optimizations such as JPS and A* are like different optimizations of a sorting algorithm such as bubble sort. Bubble sort will still be a O(k*N^2) algorithm. You might decrease the "k" factor, but it won't be any drastic improvement. HPA on the other hand is a divide and conquer algorithm, and much like "Merge Sort" in comparison. You don't get rid of the exponential, but you divide by q^2, q = gridsize. I haven't heard much about the others you mention, but at quick glance RSR seems very similar to this. My results using this was roughly an increase in performance by a factor of 100-1000 compared to regular A*, and it was fast enough for my needs. That fact that it's pretty simple to understand and implement sealed the deal. I'm sure there are other ways out there though.
I love this amazing game, and with this video I love it more!
Amazing!
This was a great talk, thank you very much!
this is incredible stuff man
love your explainig style!
This is an amazing video. Towards the end of the video, I saw a large-scale crowd similar to that in Cities: Skylines. Another question is, is it possible to modify this algorithm to prevent collisions between moving people without significantly increasing computational complexity?
Thank you. No, I honestly don't know how to do that, but I think it will need colossal computational power, unless someone has figured out some genius algorithm for it. What I do is that when I make a detail path, I iterate that path and increase the 'walk-penalty' for each tile in it it. That way there is a high probability that the next similar path will choose another "lane". It is far from perfect though.
Ontop of my last response, I have one question regarding the video content itself. Is there a handler that handles the simulation for all of the pawns, or do they each simulate individually? How much simulation runs on each of the pawns?
It seems there is an interest for this despite all. I actually don't mind making these videos, but I don't want to promise anything in regards to the KS. The AI and updating all the pawns sounds like stuff for a new video. In short, it runs on each pawn. I'll try to do that next!
Would love to understand the borders between components how you cache those and make the paths at the higher level.
That game looks kinda neat.
And the video was interesting.
Question, i realize the short "part of the way" paths solve this. But would drawing a line from A to B, then check which of the tiles are ok to path, then only flood from the tiles that are not ok to path work?
Dunno if my wording gets my question accross.
If I understand you correctly, you want to take advantage of the possibility that there might be a straight path from A to B, and if it's semi-blocked by something, still take advantage of the straight-ness. Yes, I think you could do that, I've pondered it myself, but it doesn't work well for me. Firstly, paths are usually never straight, the map will form up like a maze of walls quite quickly. Secondly, I've got roads and stuff on the map, so the straight path isn't always the best. It could be a big detour, covered by roads. Or there could be non-blocking, but slowing down tiles like water, or rubble on the straight path. If you don't have these problems, then I suppose you could also do A*, which will try to go straight to B. I don't think there's much gain to be had from first trying out a straight path, then do regular pathfinding if that fails, compared to just regular pathfinding only, if you have a fast implementation. If a straight path exists, then A* will not examine many more tiles that an iteration. That's just my opinion, thanks for the question!
Cool video, would enjoy more like this.
I'm a bit late to the discussion, but this is such a fantastic explanation. Have you experimented with variable walk speeds on the citizens? I'm curious if having a slight difference in the movement speed would have any effect on the computations and ultimately make the movements on the map look more organic.
yes, they have that already. It can cause some problems if the variations are big when they join up in divisions and try to march, other from that it's no big problem.
@@songsofsyxofficial9516 Fantastic, thanks for the reply.
How does this apply to a very dense maze? How can you calculate whether your "zoomed out" grid can connect with each of its neighbors. It seems like you'll just have to do the regular A* for each tile anyway, because you need to do A* when you're inside the chunk, and if that fails you need to zoom back out and check the neighboring chunks.
I understand how this generally can be applied to a game like yours with wide open terrain, but maybe a more dense dungeon crawler/rougelike wouldn't see as much benefit? I always figured the way I'd handle this situation would be to do a "queue" of sorts and only calculate so many paths per tick.
In wide-open terrain, A* usually beats this thing, as the path is straight and you don't benefit from narrowing the search down. It is in more dese, dungeon-like, or my case city-like maps, that it really shines. Each chunk is processed using a regular flood fill on the detail level to find the distance and connectivity to other chunks. This needs to be done once for the whole grid, then it can be done on small parts of the grid as obstacles appear. If a chunk has an obstacle running through it, it becomes two chunks. A chunk must always be connected, an open space. The zoomed out grid always needs to cover the entire map and be up to date. If a search on the "zoomed out" search fails, there isn't a path and no need for a detailed A*. It also works the other way around. You never go back and forth and try different things. I hope this answers your question somewhat?
@@songsofsyxofficial9516 So if my understanding of what you are doing is good, everytime something change in one of your chunks you apply something similar to this ua-cam.com/video/Bspb9g9nTto/v-deo.html in it ?
@@yanyankelevich2564 Yes indeed!
I imagine pathfinding is one of the main bottleneck for a game with many many entities, right? So I have a few questions on further optimizations:
Does an entity start walking along a path that is not completely computed yet?
Also, do entities going to the same general area share parts of their computed paths, perhaps as some kind of path cache? I guess HPA would make path sharing a bit simpler for entities in the same component going to the same neighbor component. As I understand HPA, it is already kind of doing that but maybe it can be improved further at the component grid level?
And for my last question, is there some kind of path reuse for entities planning to go somewhere and come back, or for similar things? (since I imagine all these paths are always bidirectionals)
But of course, it is already very impressive as it is, and the rest of the game too!
Hello! Yes, I'd say is a major bottleneck in most strategy games, even for smaller nr of entities. To answer your questions:
1. Yes, they always do a full "big chuck path", then only make a detailed path from one chunk to the next. when it reaches that, it'll do another one to the next chunk, etc.
2. There is no caching of paths whatsoever. On an abstract layer, you could store a path to every other chunk, but that can quickly spiral out of control as the number of chunks grow. Basically, it's an N*N storage algo, where N is the number of chunks. It would be faster, but finding a path in the abstract grid is still fast enough.
2b.
It works for some games, but in this, there is no telling where an entity will go next and most paths are not bidirectional. An entity will go to work, find something to each, go have a bath and then go to bed. It has little fixed points, so I've chosen to skip caching them for the flexibility and simplicity that offers.
Not bad questions, I think they'll work well in other situations, but not mine AFAIK
I see that you save the units micropaths, and I assume you also save the macropahts (on the absctract grid).
That is good for performance.
But,
Do you refresh them? for instance, half way?
Or do you just let units persue huge paths just to bump up with a wall/obstacle that was not there during path generation?
(ofcourse this would not happen often)
I don't save the abstract path. I only save the detailed path from the current abstract tile to the next. Once that is walked, I grab a new full abstract path, and refind a new detailed path from the current abstract tile to the next. So the detailed path has a big chance of being correct all the way. If not, already do expensive collision detection, so it's good that it get used for various things IMO. That's the beauty of using this algo for maps that changes.
Hey i was trying to buid a game similar to this one with huge different concept but my biggest issue as a beginner programmer is building a placement system
Im trying to build a gme without any premade engines like unity ect but im having trouble creating simple systems such as this path finding and building placement systems, can you help me our? I have a great theme of my game and the placement system and pathfinding is huge part of it just sucks i can't come up with a way to implement them sufficiently
With the larger pathfinding squares, how do you decide if a square can we walked through or not? If there's a 16x16 tiles of obstacles on it it might not be immediately obvious if I can walk from 0;0 to 4;15 How is that determined? Does it sometimes fail to find a path if most of the large square "component" is unpassable but there exists a 1 tile narrow path through it, depending on which small tile you enter and exit from? And the viability of such path within a square depends on adjecent squares etc. If there's a lot of impassable terrain, I would imagine it has to calculate a local path from each edge grid on the component to each other edge grid on the component?
Each square has a centre that 'walk' to all other tiles within the square. So a square is not always a square, it can be a blob. You then path traditionally to all adjacent square centres and save all the results in the square. You then 'square path' by visiting a square neighbours, same as if you did tiles.
The centre you pick, and the size of square determines how perfect a path will end up. You can still get perfect paths by relaxing the rigidity of the search.
Found this game on youtube, looks amazing . already added it to my steam wishlist's. i heard that there was a demo but i cant find it anywhere????
The game is available on itch.io , will release on Steam in September if you prefer that platform :)
amazing stuff
Have you thinked or used probabilistic paths? You can create a estimate for where an group of individual wold be and what they wold be doing instead of calculating this for every individual.
This can be done when the player isn't looking, when he is back looking you can use the probability to guess the actual state
"what the eyes don't see the heart doesn't feel"
couldn't you use quadtrees as well to shorten the tiles that it searches?
The only question I got is how do u determine which tiles on the smaller grid connect to large grids?
For example we got a 200x200 grid, which we break into large abstract grid 50x50.
And we wanna get from 0:0 to 200:200.
Obviously we can determine the large grid path which is 0:0 > 1:1. Then we build the path in 0:0.
So how do figure out that the 50:50 is the ending tile of the larger 0:0 tile?
Also how do figure out that 0:0 large tile is connected with 1:1 large tile with corresponding smaller tiles ie 50:50 > 51:51 is the path to transition from 0:0 large square to the 1:1?
Aside from from that, the algorithm looks good.
Thanks for the video 👍
If I understand you correctly, every tile has a stored ID that is a reference to the chunk it belongs to. You need to set the ids when building and maintaining the big grid, so you just check which chunk 0:0 belongs to and which chunk 200:200 belongs to.
@@songsofsyxofficial9516 let me rephrase a bit. So u've made an abstract grid upon your actual grid.
1. Step u find a* path for that large abstract grid. For example the grid is 100x100, abstract grid is 50x50. We want to go from 0:0 to 100:100 ie just a diagonal run.
So the larger path is 0:0 -> 1:1
Now u got to find sub paths inside 0:0 abstract tile and the 1:1
So the paths would be 0:0 -> 49:49, then 50:50 -> 100:100
And my question was, how do u figure out the destination tile in the abstract tile?
0:0 -> 0:49. Why 49? Why not 48?
Hardcode this points with the wind rose position of larger tiles?
@@MrJloa ah, all right. when pathing from one abstract tile to another, I use the centre tile of the destination chunk as a destination. Then I path from my origin tile towards that centre tile. I stop as soon as I'm inside the destination chunk. Once I've reached that destination tile, I repeat the process until I'm at the chunk that actually holds the final destination tile. I then use the true destination tile as my destination.
The PDF link is 404 for me and doesn't appear to have been cached by IA. Anyone else has a copy?
How this approach will work with case of mazes for example? In maze it may be hard to estimate if you can go from one supertile to another supertile especially if the maze is periodically changing.
When the maze changes, you need to update all components once. If you build your chucks, they should be able to work in a maze as well, only more or less fractured. As the maze grows more complex, the components grow smaller and performance will start to look like regular A star eventually.
@@songsofsyxofficial9516 thank you, that's what I thought. I think its best performance is in fields with intermediate number of obstacles
Very cool. I your project as a "related topic" on Reddit.
And another question,
How units/armies take into account walls/fortifications??
For instance, the army of a Kindgdom would treat any wall constructed by them as obstacltes to be respeted.
But the army of an enemy faction should consider those walls as something walkable (because they could destroy it).
I have a couple of separate threads that calculate everything concerning divisions. Each division gets their own path. And since the divisions are few, they get to make a traditional Dijkstra's path. I use different heuristics for player/enemy. When an enemy div gets ordered to reach the throne, it makes a path with high values for impassable tiles. I then rewind the path to find the first obstacle in the path and set the division to march there. The first row of soldiers will then collide with the obstacle and start smashing it. I repeat this until I'm at the actual destination.
That is so cool!
Congratulations on putting together such an interesting simulation!
I wish the whole game industry went into this direction.
I'm tired of seeing games with 202X graphics, and the actual game has 199X mechanics.
@@alfonsoesteves5090 yes, I agree . I wish they expanded the depth and scale of games instead of polishing the surface.
Suggestions for the game.
Content*
In my opinion there should be like a region like the one in rim world wherein there are a lot of other tribes or civilizations or cities and you have to choose where you would put your starting town.
Economy like trade with other nations
War with other civilizations. like SIEGE
Online, like damn that would be sooo fucking cool.
I'm so hyped for the game dude. Keep up the good work!!!!! I love the gamee.
Thank you. That is exactly what I'm working on now :)
@@songsofsyxofficial9516 where di you post updates???.
@@Artezch A bit all over the place. If you're in the discord, I do small incremental stuff almost daily. When I'm done I do twitter, reddit and itch. It's a bit of a mess, but hope to be more communicative not that I'm over my stage freight :)
@@songsofsyxofficial9516 what is your discord???
It's okayy dudeee, as long as you constantly update us. I don't even care if you use notepad to let us read your messages lmao. Just updatess. Might I ask, what percent or how much is the game done?.
@@Artezch discord.gg/eacfCuE hope to see you there. I'd say it's 50-60% done. Hoping to start fleshing out the base building aspect of it very soon.
great, i got you !
how is ur microphone better 4 years ago
Please add an auto save feature in the game I just lost hours of work because I’m dumb and wasn’t saving as I went
Yes, I will, fear not.
A quick sidenote for the graphics.
It is nicer for the eyes when the micro-contrast (fine textures) is not distributed evenly but on important elements, like troops.
Because right now, everything has a lot of micro-contrast and scanning the map is hard and it does not look nice.
Your global contrast works pretty well. Mountains and other impassable tiles like sea are much darker from a global perspective. And water does not have as much micro-contrast as grass.
So my recommendation is that you decrease the micro-contrast (decrease the level of detail) of the grassland greatly. This would make the whole image cleaner and easier to scan, while the mountains and the troops would still give this nice pixellated but realistic look to the game.
That's a good idea!
I would appreciate a more detailed explanation of the transition between components and the overall structure of your pathfinding algorithms working togehter
I'll see what I can do
@@songsofsyxofficial9516 I second that. What exactly determines if two "components" are connected? I suppose it would be if the center tiles inside them have a path between them? If so, I guess you have to recalculate for a component when you update a tile inside it? Also, if for example a wall splits a component into two areas, I can imagine a situation where you can't path from certain tiles in one component to another without searching outside etc
@@stuffedk Yes, exactly. Every time a new tile is placed, I recreate the components surrounding it. It's not that big of a deal. I cache all changed components each tick, then I recalculate them in bulk. Connection is made if there's a path between the centers. If a wall crosses a component, it spits into two components. Components are made by flood filling the first tile in a quad. Once the fill has stopped, either by the bounds of the quad, or blocking tiles within the quad, you assign a component to the filled tiles. You do this with each non-filled tile within the quad. If you're unlucky you end up with a chessboard of quads, but usually it's 1-3 components within a quad.
You then check all paths to neighboring components and store those in the components. I also check each tile for resources, services, entities and everything that can be useful to find. That way I can quickly check if an entity has food within 150 tiles by searching this abstract grid first.
@@songsofsyxofficial9516 Thank you for the reply! I hadn't thought of dividing the components. A quick follow up if I may, once you get the component path, do you then just split the path finding job into small paths between each center of the components? Or do you sometimes allow for longer (more natural looking) paths. and if so what kind of heuristic do you use to decide this?
@@stuffedk Good question! I do 3 components at a time(A,B,C) and I find a path from the start position I have in A, to the center of C. I restrict the search to the tiles of A,B and C, and stop once I've reached a tile in C. the center of C is just used as heuristics for the A* that does the detailed path. Once an entity reaches the tile in C, the process starts over. This gives me quite nice looking paths without too much weirdness.
I posted a crapy suggestion on steam, I wanna say thank you. My fellow Svensker, bra jobba. NotMehow
30k entities all pathfinding on A*? How big is each component subgrid? I'm amazed that you can handle so many pathfinding agents at once. It looks like each unit has independent paths, so is it correct to say you are not using flow fields? What language is your game written in? I'm curious because you seem to have made something extremely performant :)
Thank you! Yes, you're correct. The map is changing rapidly and the paths creation takes all kinds of dynamic weights into account, so trying to cache the paths or something that would speed up things wouldn't be worth it. The grid size i picked is 16x16 tiles. There no science behind it, it's just what ran fastest in my case. There is still a lot to explore with this algorithm though, it's exciting. Game is written in Java.
@@songsofsyxofficial9516 Interesting, thanks for the quick reply. And so the micro path is not calculated until the unit enters that component-right? And so are each of the components using a heuristic to find their paths with neighboring nodes? Or each abstract grid tile is considered equally distant to its neighbors, or the distances between abstract macro grid tiles are updated as the map changes?
@@GlobusTheGreat The micro path is calculated for 3 chunks ahead. Each chunk has a cache of its neighbours and the distance to them, so heuristics is used. Any time the map changes, I mark the chunks affected and re-init them. They cache basically all pathing information in them, service, other entities, jobs, resources and such, so that this can be found with a chunk path.
@@songsofsyxofficial9516 thank you :)
im just glat trees dont obstruct movement, otherwize sub regions would get distorted alot
This looks amazing, the kind of game i like haha
Cool!
Na próxima atualização coloque ponte e ponte com portões
Now that you got cash, are you planning to hire someone to help you reduce the workload and increase the rate of updates?
definitely
My plan is to keep a close eye on future mods and buy the assets I/the community likes and collaborate with someone who stands out. Until then, I'm definitely on the lookout for a pixel artist that does normal maps, but I'm very picky. I don't have that much cash to throw around yet either, considering I still need to work on this for years, but hopefully more hype and sales is on the way.
This is very similar to Tynan Sylvester's solution to RimWorld. He has an old video on it: ua-cam.com/video/RMBQn_sg7DA/v-deo.html .
You forgot to link the UA-cam video you used!
I forgot which one it was. It was a long time ago. I think it was done by the same guys that published the paper.
@@songsofsyxofficial9516 ah I see.
Well, in any case I learnt something new and you got a new person following your game from close. You basically are building an idea I had for a game so long ago, I used to think it on this scale, but starting as a single character in an RPG style / Minecraft/Terraria, with an endgame of city/colony sim
I can't wait for future updates, best of luck in your Kickstarter
"chateau" Frenchy french touchy touch here >_>
that was a nasty cough at 9:21 you can even hear it taking your breathe away.
Hunreeedddaaaahhhhhhhhgggggcaaaaaarruuuukkkhu hu hu hu
Awesome game btw