November 21, 2013 | Dukus | 104 Comments
A while back, I wrote about pathfinding and how the townsfolk in Banished figure out how to get from one place to another. I'll quote myself here. Pathfinding is the one system in the game that I am constantly fixing and making better. I’ll think I’ve gotten it right, and two months later... While the problem of getting of the AI from point A to point B solved, I've lately been hearing feedback about where the townsfolk decide to go. This is even more true since I adding the pathing tool and you can easily see where people are relative to their workplace. The problem is that when townsfolk decide where to go, they pick the closest accessible location and use it. While using closest linear distance works, the closest location isn't always the best. Sometimes walking distance far exceeds linear distance. While this isn't technically a bug, it certainly causes issues in large sprawling towns and requires a little attention. Here's an simple example of a bad decision. The workers in the house below used linear distance to determine where to work. When they actually go to work, they find a long path there - all the way down to the bridge and back. This is fine and the simulation works - but it could be more optimal. This isn't just for workplace either. It's for deciding where to pickup food and firewood, which school to use, what market to use, where to find resource to make tools, etc I could just let players deal with the issue or build more bridges, but I decided to take a day (or two) and see if I could come up with a fast way of quickly determining walking distance without resorting to doing full path finding. Finding walking distance using the current path finding system is really slow. To use the current path finding system to make AI decisions would be so slow that the game would run at single digit frame rates. The AI considers a potentially large set of locations when deciding where to go. It's just too many paths to examine. I first thought about caching paths from critical interact points, but this soon became unwieldy. There's really not a good way to know when a cached path becomes invalid or gets worse or better due to players adding and removing objects. And once the cache is filled with ten thousands, or a hundred thousand paths, storage and memory becomes a big issue. So forget caching these. After a lot of thought, and talking the problem over with some other programmers, I came up with a solution to try out, and it ended up working very well. The reason path finding is slow is simply the size of the data set - A large map has about 250,000 nodes and searching it takes time. The data is fine grained and looks like this. What I wanted to do is reduce this data set into something simpler that still mimics the basic paths people will take. So the map is now broken into larger chunks defined by where characters are allowed to walk. The problem arises where a chunk has disconnected parts. For example one chunk could have river running through it that cuts it in half - that chunk has to be broken into multiple pieces so that there is a distinction between one side of the river and the other. After breaking into blocks and resolving any disconnected regions, I arrive at the simplified pathing data set. The colors just represent distinct areas. One nice feature of this data set is that it can be updated quickly. If a new building is added, or a building is removed, only the chunks that intersect the new building need to be recomputed - and this process is really fast. The next step is to connect each distinct region to the others and maintain connectivity information. Again updating this is fast as when a region changes, only it and its neighbors need to recompute connections. Once the connections are built I end up with a graph that represents a general but simplified map of how and where people in the game can move. Using A* on this graph computes paths and distances at anywhere from 60 to 100 times faster than the more complex and fine grained path finder. This is used in place of all previous checks for linear distance. While the distances are coarse estimates, what results is that people find a decent idea of walking distance rather than looking at pure linear distance. The people then decide to move into the more logical homes. While the distance estimates are fast to compute, they aren't instantaneous. But because the data set is simple and fairly small, caching the distance between to areas actually works for them. The paths are cached for only a short time. The hit rate on the cache is very high, and makes the slight delay of the cache worth the time savings. Once in a while people do check to see if there is a better way to get to a workplace, and they'll move. Here I've built an additional bridge, and as the new estimate distance is shorter, the workers move to the closest home after a few months. Somewhat related, because this path finding method is so much faster, I've got a note to make regular path finding use it. The basic idea would be do perform the coarse path find, and then when computing a path on the fine grid, only areas touched by the coarse grid would be available for A* to consider - instead of considering the entire map. From a code design and performance standpoint, this is a fairly elegant solution and I can make it generic and reusable for any set of nodes - not just a grid. But that's a task for another day, another game. This was a great two days of problem solving and it fixed a major AI issue, but this wasn't a change I really want to make this late in development. I'm starting to get a little nervous about making big changes to existing systems - and really examining what changes I make and how they are made. I considered reverting my changes several times, because I really don't want to add new bugs at this point. But it makes the AI so much smarter looking and optimizes worker time so well that in the end it's worth it and makes sprawling towns work better. The game is definitely shaping up. I currently don't have any crash bugs to track down, and most of the current issues I have open are simple AI and user interface issues. Getting there!
Great read, thanks 🙂
This is indeed, well it wasn't a bug, rather a technical issue but great you have changed this.
Please please please release a beta, I'm dying to play it 🙁
Stelly
Another great update! Keep up the stellar work!
Does the house need to be empty/vacant for the villagers to move into it? Or does this push an existing family out therefore forcing that family to find new residence too?
One of the worst things about the new SimCity was finding out no Sims actually had set residences. They just went home to the closest vacant home everyday.
Keep up the good work. I always find bug tracking to be the worst part of programming, but coming up with solutions is often the most enlightening. You often have to learn more to fix the old problems.
Since you are releasing on steam, i would track down the last of the major bugs and leave many of the minor bugs for a bit late. In this world of digital releases patching is simple. Fixing up bugs and adding new features you wanted to see but never had time can always come later. It may end up critics have something entirely different they dislike and you may want to fix that instead. Playtesting is one thing, but in my experience you never get all of the bugs/problematic features out before release.
It took you two days to determine and implement a solution! You get so much accomplished in one day. I am jealous! You should write some posts on tricks you use to stay focused and increase productivity. I am blown away by what you can accomplish in a relatively short amount of time.
I have been lurking, reading every post twice and watching every piece of media tens of times, without leaving a comment.
This is a day one purchase for me, and my expectations are so high. A city builder is exactly what I'm looking for, and since SimCity didn't turn out great, I'm even more stoked for Banished.
Anyways, I just wanted to say: Keep up the good work, and please please please don't dissapoint me.
keep it up!
love how you keep us up to date on the bug fixes and how the game comes evolves, never seen it like this.
cant wait to buy this game!
When can I give you my money?
I've noticed in your videos that when you rotate, the foliage rotates with the screen. Is this intended, or will it be changed before release?
I guess some people wouldn't care, but something like that is really hard for me to look past when my eyes constantly catch onto it.
That's a lovely solution to a complex issue, well done.
release a beta for few people willing to pay more. They will help you discover new bugs before you get the game released to everyone!
(Planetary annihlation did this)
Oh the anxiety. Ps4? Xbox one? Nope! Banished is what I'm anxiously awaiting. Oh and the next prison architect alpha.
I'm almost going to be a little sad to see the game released, if for no other reason than I don't get any more insightful programming-related posts. Great job keeping your updates both technical and interesting!
Did you consider using A* JPS for pathfinding? It's a very large optimization on A*, if you have the right kind of pathfinding nodes.
I hate to say this, but I think you may be making the game TOO efficient. In real life, people don't behave like this. I work 8 miles from home. There's a bank and a pizza place right next to my house. Why not work there? Simple. I do not have the skills for one job and the other doesn't pay as well as the skills I do have. So why not move closer to work? Because other people also want to move closer to work, which drives up the cost of housing.
It seems like the system you have implemented disregards land values and incomes and simply lets people move into whatever house they want so that they're close to where they work. It also sounds as though people will move in with other random strangers willy nilly as long as the house is near their work. Is there anything to take into account family? If a husband is a fisherman and a wife makes clothing and three kids have farm jobs or go to school, where do they live? Does the husband live near the docks while the kids stay with total strangers on the farm?
Hey developer guy. This game looks like the game of the century, and I am looking so much forward to it, it's just unbelievable. I even started playing some Dwarf Fortress again to warm up for this game. So, I really want a beta of this game to be released, or the game itself.
However, after reading today's update, I am left with a feeling that the amount of progress you seem to do every single day is just too great to release the game until you know for sure that there are no more important things to fix.
TL;DR: I really wanna play this game, but if you think waiting a bit more is the right thing, then that is ok too I guess.
Dear Santa, I only have 1 wish for christmas and it's a PC-game called Banished. I would do anything to get it and I promise to take care of more homeless cats and dogs just to get better karma to get this game. Please Santa, make me a happy boy!
Sounds like you just independently invented HPA* (http://aigamedev.com/open/review/near-optimal-hierarchical-pathfinding/). Nice work. 🙂
I await this game with great anticipation! I haven't found a great city builder like this appears to be in far too long. It's also so much fun to read your posts and keep up with the development of the game! Can't wait for release!
Wow, it's amazing the extent you are going to to release a polished game. For a development studio of one this is more than commendable. I have always considered flaws in the logic of the game 'bugs' as well. To me if the game doesn't work as desired, or as one would think it should, then it is a bug. Cu-dose to you my friend.
If half the development teams out there were a diligent as you I would have much less frustration with most of the titles released today.
There is a small part of me that keeps thinking, just release it, we will pay for it, find the bugs for you and you can patch it. But I know what you are doing is right, and will be worth it. It's only my impatience that's making me think this way. I'm sure after you do release, there will still be some bugs that people find, once it is in millions of people hands 🙂 But there will be significantly less considering how meticulous you have been.
Grant,
I don't think your criticism applies to this game. Remember the scenario of this game. This is a group of people who are banished, and must work together to survive and prosper. They would not suffer from superficialities like property values, and living in the sub-urbs.
Martin - The law of supply and demand is not at all superficial and still applies to these people. In fact, it may apply even more than it would in an established society because there are fewer rules and regulations restricting free trade. Land, fish, ore, crops, etc. are all finite resources and they all have value. Changes in the supply and demand of these resources would certainly constrain where people can live and work. Not to mention other factors such as the desire for material goods (nobody wants to live in a one room shack if there's an mansion next door for the same price), increasing and declining demand for certain goods (wheat is more valuable in the winter, few people will want to eat potatoes if there is cheap meat, fish, and fruit available, etc).
I'm not saying that Banished needs to account for all of these factors, but simply making simulated people live in the closest house and while disregarding everything else does not seem to me to be an elegant solution.
I've got to say I am really loving the technical posts. Seeing what problems you go through and how you solve them is always extremely fascinating.
Loving these updates. Can't wait for the game.
One step closer to release! Im hoping for a Christmas release, btw. 🙂
Great solution! Thanks for going the extra mile and coming up with a beyond satisfactory solution. This is not what the SimCity folks did in their latest game and it shows.
Another interesting blog. This is so nice to read.
It reminds me of what a dev of Age Of Empires 2 said, Matt Pritchard, about pathing. It's somewhere (sorry) between the middle and end of this topic (page 48 at the moment).
http://aok.heavengames.com/cgi-bin/aokcgi/display.cgi?action=st&fn=3&tn=40110&f=,,,&st=0
I'm looking forward to every post to come, it's really fascinating!
Looking good. Thanks for sharing!
Nice work in implementing heuristic pathfinding algorithm.
But don't be afraid to add even more heuristic levels. Adding just one aditional level could quickly alow you to check if it is even posible to cross the river (each side of river band is its own region).
This could also become usefull if you at some time implement ability to build wals and therefore create enclosured regions.
Is there a small chance it will releas on Christmas, or 31 December-1 January? It whould be cool. Really awsome game, and I've bin following it since the start. Can't wait!
Good read.
Thanks for solving the issue/adding that new logic so late in the development.
As a future buyer I do appreciate it 🙂
can't wait to play it! so much detail, passion and love in it
To those who are complaining that having the townspeople using the nearest possible buildings to the worksite is not realistic:
Realistic does not always equate to fun. Remember, it's a game. It might be a simulation game, but it is, nonetheless, a game. Having needlessly inefficient placement of citizens is going to bog down your gameplay and make things tedious, not fun. This is solid work by the dev.
What about trying to offload some of that mathematical nightmare to a GPU instead? oodles of number crushing goodness in most peoples machines... use it. 🙂
Luke you are "Fabulous". I know little of wait I know nothing when it comes to what you are achieving, somehow you explain it in a way I actually understand. We are all looking forward to the masterpiece that you will soon bestow upon us, this niche of a game, has many followers and grows daily. We as a collective, I am sure salute you, not only for developing the game, but for the regular updates.
I love the committment you put into making a polished game before release, especially the focus you place on the AI.
So many games today released with such backward AI and pathfinding that it completely ruins the experience
Do you mind teasing us with more information about the extend and length of the bug list?
Even just rough count of items on the to-do list would be cool.
it's just like Finite Element Analysis using big chunky elements.... except it's 2D
you could have factored in gradients for hills!
do you have big hills in this game??
yeah some games I used to play had retarded path finding!
I'm glad you fixed this. Bad pathfinding is the bane of many games and a lot of big companies just say "screw it that'll do". I'm glad you could come up with a good solution.
Maybe if you spent more time on making the game acually work properly Instead of writing these 5000 paragraph eassays about why the game doesn't work then maybe you would get somwhere.
Iv been waiting on this game for a good while now just like ever last one of us, and yet the due date you mediated to all of your buyers has yet to show anyform of truth. At this rate the game might come out by the end of next year. :/
I mean come on dude. We all are thinking the same thing!
We are basically telling you to take our money as we throw it in your face!
Just saying.
@Cameron: The most cursory of glances at the comments here would have told you that you're not in fact saying what everyone is thinking. Many of us appreciate these posts and are enthusiastic enough about this game that we're willing to be patient for a top-quality release.
I agree, waiting for a polished game, played how Luke envisions is much more appealing than something that'll be bug-ridden an un-optimized.
Sure I want to play the game, but I want it to be as good as it can realistically be before release. Not to mention that, like most people, I enjoy these updates a great deal and really appreciate the effort Luke puts into them.
Why is it so bad that he is trying to share his thoughts, views and processes during development, it's been a unique insight and you should just be glad about it.
Don't forget by the way, the release date was always 'Late 2013', by my count December 31st is still late 2013. His game, his time, let him do it how he wants and keep them comments to yourself.
Arrrgh.... you're torturing us just by posting those these developer diaries. Can we just give you our money now?
i really want to give you my money!
please just give us a release date 🙂
“Patience is bitter, but its fruit is sweet.”
― Aristotle
Love to read these sorts of posts 😀 Please never stop doing these posts and keep the good work up. 🙂
As others have said: Take your time and do your thing. I'm sure the wait will be worth it.
Do understand though that for those who opted to "hold their breath" until they either turned blue or got the game, thing are getting desperate. Think of the children sir.... 😉
If you are thinking on upgrading this game often, do it like minecraft...
Sory for my english...
I'd like to say the complete oposite of some commetns here.
Please don't give us a release date. Release dates are bad in two ways:
1) It adds unnecessary pressure on the dev when bugs are more complex than expected. Which might result in the release of a bugged game which nobody likes.
2) When the deadline isn't accomplished on time for the sake of releasing a finished, stable and fun game a certain group of people will start whining and demanding in a very rude way.
So no release dates please, that's better for everyone. Btw I'll say it again, I love the blogs. 🙂
Another blogpost! Yey! As an amateurprogrammer myself, i really enjoy reading about the inner working of what has to be the game of the decade!
Will the game auto-update itself? You seem like the type to always want to fix everything quickly 🙂
Something I'd like to mention (and completely off-topic): the forums are currently being spammed by 2 users. All random advertisements. I hope they get banned.
I wanted to mention it here so it gets faster attention.
this is quite fun and intreesting read
can't wait for this game and I hope it be great work!
I love reading all the updates, cant wait till release. Please, Please, Please give us a date soon
Can you give us a release date? On which date of December?
Thanks for the feedback. Can't wait to play the game.
ima laugh when this game dont even get released and all ya people have been posting and waiting so long... games do tend to fade even in development and never get released oh the agany however its spelled lol
When Can I give you my money?
It has come to my attention that as being the co owner of this project, I am now left to inform everyone on this page that the game is no longer in development and has been canceled due to funding. there was to many tech issues to keep the development of the game going. again we are sorry to inform everyone of this but the game is no longer in development.
@John I wonder at what point a troll could be sued for posting false and potentially damaging information on a game website? Just curious.
@Sarayakat
Pretty much at the point of john's post. I'd like to see a guy like that outed and then sued for something that stupid.
Then again, who is going to believe an anonymous person on a blog site. If it was cancelled, the news would be in a blog of it's own... "Do not feed the troll"
@ Fr8monkey: Ordinarily I would agree, but this one decided to identify himself as "co owner", a false (afaik) and possibly actionable claim. I did struggle a bit with the "don't feed the trolls" rule though.
Can't wait to play this game. I love how mellow it looks. Just the thing for a winter evening.
I can say that I funded the whole idea... don't make it true 😉
So is this game is going to be free? If not is there a way to buy it without credit card or SMS?
No... Get real!
@ Random Just give someone a friend/family the money and they will buy it for you over the net.
Now you should go and help EA out with Sim City now. They need it.
2 days well spent imo, this is a key feature people are really going to appreciate even if they don't know it exists. good to know we can spend more time building, and less time raging at this guy who would rather live across the river.
This was actually really helpful for me, another programmer here.
I think that writing these little blogs creates time to reflect on what the game is and where it's going. It creates a virtuous feedback loop.
Plus you don't want to burn yourself out on the technical stuff. Sometimes there are frustrations and you gotta get some things off your chest... hence the blog!
I don't think writing these blogs takes as much time as people think. Plus it's publicity!
I'm certainly not going to complain about taking time out to write a blog when the developer can resolve a problem like this in 2 days flat. We all know big-studio games that haven't bothered to patch in good path finding at all despite how badly many of their games have needed it.
We don't need to tell him that there's an advantage to shipping well before Christmas, but there's also an advantage to getting really high review ratings. For a lot of people who haven't been following the game, the decision to buy will be taken on just how good the reviewers think it is when it pops up on Steam. Taking the time to polish could make all the difference between seeing the game succeed so well we get years of enhancements and expansions or not.
Yeehah, enjoy enjoy enjoy! Mind to send me a signed boxed edition of the game, mail me for address and details 🙂
Awesome read! Looking forward to the release very much.
Keep up the excellent work.
I am really looking forward to this being released. While I am hoping for a December release, if a delay is needed to ensure the game is polished off, I would be happy to wait. Just look at games like Battlefield 4, SimCity, and so on. All released full of bugs that prevented lots of users from enjoying the game... or even playing it!!!
As for the blogs, they would take up a minor portion of time compared to the games development and bug fixing, yet provided an essential services to us customers. It keeps us informed as to how the game is going, how close we are to release and allows the developer to get feedback. There has already been some changes from posts in these blogs. It's just a shame some of the large development companies can't do the same.
Cannot wait for this game to be released.
@Cameron, I'm sure it's been pointed out to you how much of an idiot you are and how you absolutely do not speak for the vast majority of us, but to add: The release has been scheduled for "late 2013" for ages now, he has until the 31st of December to still be on schedule. However, a month or two over schedule isn't the end of the world either. On top of that, he doesn't have to spend 24 hours a day, 7 days a week making this game just because you're impatient. You have no idea when he wrote this blog post, he might have done it on his own time after he'd finished work.
This is exactly the kind of game I've been hoping/waiting/searching desperately for! I'm sad to see that it's only going to be released for PC, though... I have a Mac. Please release for Mac at some point - you'd have a ton of business coming in from that end, I can guarantee!
please release this game before christmas..
@PROTHO
NO NO NO !!!
This game must be released when it is finished !
Personally I wish he would at least give a estimated release date range, with all the sales coming up and such.
Hey there! found this game on steam and I'm really looking forward to try it!
It looks absolutely fabulous - it seems to have the features I felt simcity lacked.
Keep up the great work!
Angie
@Lexie On an Intel mac, you can install Windows with bootcamp. It doesn't take a lot of time. I already did that so I'll be able to play Banished the day it comes out !
Just wanted to say that I'm looking forward to this game probably more than any other game there is.
That being said, please make sure that you take time to enjoy your holidays. 🙂
Any particular reason that "banished" is an invalid answer to the forum registration question?
Also, there's a bunch of russian spam cluttering the board, you should take a look at that.
I'm all sweaty waiting for this game to come out already.
It is a shame to see so many trolls on what was a once very respected site. Some of these people are just plain out rude!
If people are so dispirit for a "better" city builder game then they can make one themselves! I Feel the need to post this to encourage the developer to continue to post his updates as I very much enjoy learning about game creation and what types of "glitches" this game has encountered along the way. Thank you very much!
P.S. Please take into consideration deleting some certain post above as they contain criminal slander.
Duffman you're right. Although I think deleting posts isn't going to help.
Release dates are not a good idea, it add unnecessary stress and confusing (and rage somehow) when they can't be accomplished.
I've seen that within the KSP community in 2011.
A indication that say how many bugs have been finished would be nice... but in the develop world solving bugs mostly makes new bugs appear. So that indication would be a rough estimate which tends to change a lot.
I think that the current cycle of blogs and progress updates is the way to go. We can see the horizon but don't know exactly how far we have to walk. 🙂
Add one more thoroughly disgusted SimCity user to the growing ranks of the wanting for Banished.
and one more here waiting for Banished as a replacement to "shame city 5"
We need more news about the game !!! :DD
Hey, my comment was not rude. I am literally sweating of excitement for this game to be released. so suck it duff.
I'm waiting with patience (somewhat :P) on the release of this game.
There shouldn't be a release date anounced until you're absolutely sure it will be released on that date. Otherwise the kids will stay home from school to play this game, while in fact they shouldn't...
hey you still alive buddy ?
Please take my money and give me the game!
I'm sure it's a fake game and blog to analyze our gamer social comportement and how many time we can stay without news from the game we are fan (and known "nothing" on it) ...
please, give us news 😀
I too came here whilst looking for something to take the place of "the city-builder whose name shall not be spoken". Tropico 4 is keeping me happy in the meantime, but I will drop it in a hot second when this comes out. Love the setting and the ambience. Already budgeted, ready to buy. 🙂
Edit: Hoping the long silence is due to the imminence of release!
SILIAN: "I’m sure it’s a fake game and blog to analyze our gamer social comportement and how many time we can stay without news from the game we are fan (and known “nothing” on it)…"
No, this should be CIVITAS:
http://civitasgame.com/
Those guys hyped everybody with a KickStarter, went private funding and we never heard a word after the website said, back in MARCH, that the BETA would be VERY SOON... I'm betting that March/25th Beta post will make it first anniversary before any News...
That just looks like a scam londrer.
And guys, it hasn't been -that- long since the last update. It's only a similar gap to that between the blog post on the 23rd october and the one after it.
fryshutuptakemoney.gif
But seriously; interesting read.
Çucikum śultumá Āero beneddi flœn Çœił!
@genma
this is a reply to your reply about my question concerning mouse clipping in a previous post: http://shiningrocksoftware.com/?p=1724.
I'm replying here because that forum is now closed.
THANKS for the info!
Indeed, even though I am an above average computer user (yes, I was already aware of AutoHotkey), I'm not a dev or have any skills in coding...yet. So, it was really cool your tip on ClipCursor function within Windows. Of course, that seems not to solve the issue on its own and some sort of script stills needs to be assembled to somehow superimpose ClipCursor over native game window that was programmed without it.
Either way, I did another search on such scripts and ended up still not finding one that actually translates hitting the edge of a mouse-clipped window into a game scroll. But, I did stumbled on a super-cool software that even though is designed to tweak DirectX parameters, ends up getting really close to that aim. I have tested it and now the scroll edges are quite near the game window. So now I can play windowed mode (crisp graphics) and scroll swiftly with the mouse :D.
errr, I'm not sure if I can, so for respect to ShiningRock I'm not advertising such software here. But it is free, open-source, geek/user/dev-designed and super-trustworthy tool.
Cheers to all.
PS- release! 😉
I love reading your technical explanations of the challenges you face while building this wonderful looking game. Please continue these awesome posts!
-Matt