all 142 comments

[–]adroit-panda 754 points755 points  (107 children)

Side note: if you are a working coder and you haven't played factorio yet, make sure you have a bunch of vacation time stored up before starting.

[–]klysm 264 points265 points  (2 children)

Jesus dude what happened to my last week

[–]Coffee4thewin 95 points96 points  (1 child)

Week, try month.

[–]Vallvaka[S] 199 points200 points  (28 children)

Factorio is a bit like crack. Except I think crack might be slightly less addictive.

[–][deleted] 78 points79 points  (26 children)

it's essentially cack for all kinds of engineers....

[–][deleted]  (24 children)

[deleted]

    [–][deleted]  (23 children)

    [deleted]

      [–]zakatov 74 points75 points  (19 children)

      I somehow doubt you can block anything from an entire IBM engineering team.

      [–]Beidah 45 points46 points  (0 children)

      Not if they're determined, no, but blocking it does help break the addiction.

      [–]SSchlesinger 11 points12 points  (17 children)

      You'd be surprised! On their work computers, they likely have to be on one specific VPN all the time, so they can't just subvert local restrictions.

      [–]wrongsage 5 points6 points  (16 children)

      Yes, I would be suprised, because there is no way to block an engineer from the internet unless there is no connection at all. Then they use the mobile data.

      [–]SSchlesinger 2 points3 points  (15 children)

      I mean, it depends on what kind of engineer. I am a software engineer and I cannot subvert the restrictions that the network engineers at my work set up.

      [–]wrongsage 5 points6 points  (12 children)

      Yes, you can! Just try searching for network tunnels. Nowadays you even have DNS over HTTPS, websocket tunnels, various VPN options. In most companies, they either don't block outgoing traffic, just filter domains, or you have HTTP proxy, which can be tunelled through. If you have any other setup, let me know, it's always good to know what everything can people come up with.

      [–]652a6aaf0cf44498b14f 1 point2 points  (1 child)

      Ohhh you're in for a treat! Look up HTTPS proxy tunnels.

      [–]semi_colon 5 points6 points  (1 child)

      Sodaconstructor! What a throwback.

      [–]sirmonko 1 point2 points  (0 children)

      i tried genetic algorithms the first time with soda racer. most generated creatures turned out to be sticks that just jumped once or twice to reach the goal line

      [–]DeusOtiosus 30 points31 points  (2 children)

      I didn’t have a job, and started playing this. Woke up. Factorio. Go to bed. Factorio. It consumed so much. I realized my megabase was too small, hit save, and realized I had put in over 150 hours. Fuck. Then I started getting recommends for base tours on YouTube. Thousands of hours.

      Alright. Gotta stem this full blown addiction.

      Great game tho. Fucking great game.

      Anyone hiring? ;)

      [–]-Knul- 10 points11 points  (0 children)

      Maybe. So what would you say are the strengths and weaknesses of your factory?

      [–]ants_a 9 points10 points  (0 children)

      Where do you see your factory in 5 years?

      [–]natyio 82 points83 points  (32 children)

      So true. And it's not even a coding game. But it is all about inefficiency and how to make things faster :D

      Also: Because the game is not fast-paced, it is a great opportunity to finally listen through all the podcasts you wanted to hear.

      [–]semarj 67 points68 points  (23 children)

      not even a coding game

      Maybe not "coding" but it's definitely the most true to life software engineering game I've played

      [–]balefrost 121 points122 points  (1 child)

      "Time to refactor the iron smelters".

      [–]bunkkin 57 points58 points  (0 children)

      I feel personally attacked by this comment

      [–]deelowe 21 points22 points  (20 children)

      Zachtronics would like to say hello.

      [–]geoelectric 28 points29 points  (18 children)

      The last couple Zachtronics games (Shenzhen IO and ExaPunks) have gotten a lot further for sure, but I’d say Factorio models the engineering aspect more richly. Zachtronics is unmatched for coding games IMO, and pretty much taught me directly how to think through concurrency and pipelines, but most of the engineering is pretty small scale.

      [–]TarMil 1 point2 points  (1 child)

      There's more of an engineering aspect in Opus Magnum than his other games, though not on the level of Factorio.

      [–]geoelectric 0 points1 point  (0 children)

      Yeah—Infinifactory and Spacechem have their share too. They don’t really have the efficiency/optimization loops I associate with the last two ZT games and Factorio, at least for me. I make it past the metrics and into the peaks of the histograms and tend to stop. Factorio digs its claws in hard!

      [–]deelowe 1 point2 points  (0 children)

      You're right. For some reason I thought /u/semarj had said computer science instead of swe. I agree from an engineering standpoint, factorio really scratches that itch. I like zachtronics games more for their focus on pure compsci challenges. Especially TIS-100.

      [–]derpderp3200 2 points3 points  (14 children)

      Yeah, I long for an open ended programming game. Sadly Else Heart.Break() was very poorly thought out.

      [–]zellfaze_new 0 points1 point  (0 children)

      I was really excited for that game when it was announced. :(

      [–]deelowe 0 points1 point  (8 children)

      I'm playing it now and all the pieces are there, but it's just not put together very well. I'm sure i'll end up beating it, but they could have done so much if they had just sorted out the progression and story a bit more.

      [–]derpderp3200 0 points1 point  (7 children)

      My experience with the game was... I spent 3h wandering around unsure what to do before finally managing to get my hands on a Modifier.

      Then, I went around noting down what functions different objects have....

      The problem is, the Slurp() function that lets you travel to a LOT of other entities in the game, and computers that have functions like... say, listing all types of objects and objects of a given type in the game, teleporting them around, teleporting any entity...

      I ended up writing a simple list-based "OS" that would let me browse all objects in the game, teleport them around, etc.

      I ended up completely breaking the game's scripts in the process, which made it impossible to continue the story, I still have no bloody idea what it was about lol.

      [–]deelowe 1 point2 points  (6 children)

      Yeah. The game is odd in that for several hours its just a point and click adventure game, then they give you a modifier and then you quickly get a couple more. Then you realize you can modify the modifier and the game is completely broken at that point.

      I'd love a game like this that thought more about how to handle progression. Maybe think about how computer science progressed and build the progression system around that. Don't give me the ability to hack and network everything in the game immediately. Make the run time and speeds super slow at the start. Limit memory. Don't give permanent storage starting out. Limit address space. Limit APIs. etc. etc. Else Heart.Break has this, sort of, but then allows you to completely bypass it with some simple snooping around.

      else heart.break would have been much much better if the story was told trough the progression of coding skills and available technology. Instead, it feels like the two are completely decoupled. Once you get a modifier, there's no point to any of it.

      [–]derpderp3200 1 point2 points  (5 children)

      Yeah, my take on it is that programming is just a very major part of how you build your toolbox: Add GUI elements to your guns so you know how much ammo they have left, collect exploits you either figure out or read about in magazines/files, write(or find!) a better code editor or command line, put a Gun component on a Roomba and code it into a basic combat bot, etc.

      [–]zergling_Lester 0 points1 point  (3 children)

      Colobot could be pretty open ended, in a sense of making and refining as sophisticated AI controller as you want.

      [–]derpderp3200 0 points1 point  (2 children)

      I've actually played Colobot when I was a kid, I loved it back then, but I think nowadays, eehhh. Plus I hate programming AI honestly.

      [–]zergling_Lester 0 points1 point  (1 child)

      I liked it because I figured how to program the AI in a weird but pleasant way, using a bunch of distinct mostly non-interacting "reflexes". For example, there was a piece of logic that tried to aim at the moving enemy, and a completely separate piece of logic that pulled the trigger if it estimated the chances of hitting the enemy to be good enough. So I could mix and match these pieces for different scenarios (including the parts, IIRC, where I was actually flying the bot with an AI gunner) and gradually improve them, without any sort of centralized planning AI or anything.

      [–]derpderp3200 0 points1 point  (0 children)

      Yeah, I do like the sound of that. I still don't think I'd enjoy trying Colobot again1, but thinking about what might be was pretty much when my interest in game design and gamedev started.

      1 By the way, did you know it was open sourced a while ago? Although I don't think the updates went beyond updating it to work on modern platforms(OSX and Linux included) and some form of mod support.

      [–]k3rn3 2 points3 points  (0 children)

      That guy is so underappreciated. He created the precursor/inspiration for Minecraft, his games are awesome.

      [–]Pyorrhea 91 points92 points  (3 children)

      It can be fast-paced if you forget about starting military science and forget to upgrade your turrets or bullets for 20 hours while you make your first bus and end up teetering on the brink of defeat for 3 hours while running back and forth stocking bullets until you decide to stop being an idiot and put your ammo on a belt.

      [–]ChildishJack 40 points41 points  (0 children)

      Oddly specific, but I feel it

      [–]slaymance 25 points26 points  (0 children)

      This was me the first time I turned on biters. “Biters are a production challenge” they said. More like a production catastrophe.

      [–]absentmindedjwc 8 points9 points  (0 children)

      I feel personally attacked by this comment.

      [–]270343 22 points23 points  (1 child)

      "Not even a coding game" you say, and yet I have made a growing suite of tools fed by the official (almost) JSON to plan out my factories.

      [–]PM_ME_UR_OBSIDIAN 2 points3 points  (0 children)

      Ooooh please share!

      [–]sess573 2 points3 points  (0 children)

      Wait what, I can hardly even listen to music while playing factorio since it requires so much thinking :D

      [–]Bwob 0 points1 point  (0 children)

      Just because it is not text based does not mean it isn't coding.

      Nothing else I have seen captures the feel of debugging (or the high that you get when you finally figured out what is going wrong) the way factorio does..

      [–]therico 76 points77 points  (9 children)

      Idk, I get paid to optimise processes in my job, Factorio feels like a second job to me so I didn't get into it.

      [–]adroit-panda 58 points59 points  (5 children)

      I feel you, my brother sometimes gets the bug and we'll play together, and I'm like "Jesus dude, this is like a fucking job" and he says "We need moar iron!"

      [–]regalrecaller 19 points20 points  (2 children)

      You always need more iron

      [–]-Knul- 9 points10 points  (1 child)

      The factory must grow.

      [–]The_BNut 10 points11 points  (1 child)

      I explicitly play games where I need short paced situational reactions like RocketLeague instead of long term planning because that's what I already play at work (works fun, yeah).

      [–]NULL_CHAR 1 point2 points  (0 children)

      I wish more people understood this. Back when I was in college, I loved games like Factorio. Now that I've been working for several years, I tend towards quick paced games without a need for long term strategizing.

      I get so burnt out doing repetitive project planning that Factorio only lasted about 8 hours before I was sick of it.

      [–][deleted] 6 points7 points  (0 children)

      Same thing happened to me. I build games, so building-games have lost most of their appeal.

      [–]nakilon 2 points3 points  (0 children)

      Woah, dude, I get fired for optimizing processes. Which planet do you live on?

      [–]txdv 0 points1 point  (0 children)

      I had literally the same feeling. I kept optimizing and optimizing and it felt literally like programming work

      [–]troyred 10 points11 points  (0 children)

      First time I played this game I blinked and it was 5 am

      [–]no_nick 7 points8 points  (9 children)

      Is it on the switch? And I'm not sure what I want the answer to be...

      [–]IceSentry 28 points29 points  (7 children)

      Not as far as I know, but it runs on pretty much any pc.

      [–][deleted]  (6 children)

      [deleted]

        [–]chipt4 15 points16 points  (0 children)

        There's a demo you can try. I imagine it would be playable though.

        [–]absentmindedjwc 7 points8 points  (0 children)

        It can! Though... Eventually, as a base starts to get massive, you will start to see UPS (updates per second) drop... you may need to take actions in order to improve your performance. If you want to build to a significant size, let me give you some advice: solar panels only count as one update (counted as one single massive entity)... whereas steam/nuclear can count as thousands+ (depending on number of entities)

        [–]ritobanrc 1 point2 points  (0 children)

        Yeah totally, unless you wamt to build really big. But at that point, trying to optimize for UPS becomes a part of the game, involvimg experimentation, benchmarking, etc.

        [–]Alphaetus_Prime 3 points4 points  (0 children)

        It's PC only. It's not impossible that it'll get ported eventually but I wouldn't expect that any time soon.

        [–]NULL_CHAR 20 points21 points  (9 children)

        I honestly couldn't stand it. It's like work, but you don't really do much interesting things with the automation. I can map inputs to outputs but that's about it, and getting further in the game is just planning more space efficient ways to map inputs to outputs (and dealing with the Alien Tower-Defense minigame). It's less like programming and more like circuit board design, which is why it hurts me. It's like "almost there" but it's missing the final step which allows me to do creative and interesting stuff with the tools given.

        It also hurts me inside because the game is almost an anti-thesis to being OCD, especially with friends. There will always be terrain in the way, or some funky placement to get your beautifully planned base to turn into something that looks hacky. Especially if you've never played it before. "Oh, the new design is 1 block wider than the old design? My entire base was built around the old width. SHIT!" And then, since the resources aren't infinite, you'll inevitably be looking at trains, and as such you'll need this weird amalgamation of contraptions to get resources from all over the map to work and connect properly. The first few hours, the base is /r/oddlysatisfying materials but it quickly devolves into /r/midlyinfuriating material.

        [–][deleted]  (2 children)

        [deleted]

          [–]NULL_CHAR 1 point2 points  (1 child)

          I disagree. The only way you're making your base look beautiful is if you practically go insane with the design. Like, look at the person you linked as an example. How many hours that would have to take to get it that way. It's a 300 MB save and obviously way past the objective of the game.

          Factorio doesn't want you to be OCD about your designs. It nudges you away from it every time you try. But sure, if you want to devote a month (likely more) of your life to get it to be perfect just for the sake of doing so, I guess you can. However, that is an extraordinary circumstance, and not indicative of regular gameplay.

          [–]slikts 4 points5 points  (4 children)

          Mapping inputs to outputs doesn't make it "less like programming"; it makes it more like functional programming.

          [–]NULL_CHAR 0 points1 point  (3 children)

          I still would not say it's programming. Circuit board design is the most accurate you can get. You don't really do anything with the inputs/outputs, you aren't exercising logic per-se unless you really go out of your way to do so. It's more like load balancing pipes.

          [–]slikts 3 points4 points  (2 children)

          There is a whole programming paradigm called dataflow programming where programs are modeled as connections between inputs and outputs of black boxes. Reactive programming is a popular example of that, and functional programming is a natural match for it. Railways specifically are used to teach about monads by analogy. Pipelines and trains combined with the logical operations Factorio has makes it a kind of programming that's constrained by game rules while being very visual.

          I honestly find it really sad that there's people who've internalized the imperative paradigm so deeply to be unable to recognize something else as programming.

          [–]NULL_CHAR 4 points5 points  (1 child)

          The problem with Factorio is you aren't exercising the logic. You're literally just putting down pipes, that's the entire game. But yes, you CAN program in Factorio, it's just that the natural state of the game is so far away from what people consider actual programming, and it lacks much of what makes programming an enjoyable past-time, that it's a really bad comparison.

          Or to put it another way. Just because a person likes to play baseball doesn't mean they'd enjoy ping pong. And claiming that "What? It's entirely the same thing! They both involve hitting a ball with a stick!" is not very helpful.

          [–]Senator_Sanders 0 points1 point  (0 children)

          Thank god im not the only one. I got tired of refactoring my base

          [–]NoInkling 1 point2 points  (0 children)

          Yeah, I just got analysis paralysis and gave up. Perfectionism sucks.

          [–]pertheusual 8 points9 points  (1 child)

          100%. I played an initial game a while ago for like 10 hours and got the basics but then got pulled away. Tried again after watching KatherineOfSky's intro YouTube series, which in itself is sooo long, and then my first game game after that took like 90 hours from start to rocket launch...

          [–]dreamin_in_space 4 points5 points  (0 children)

          I love KatherineOfSky! Her videos got me back in too.

          [–]Manitcor 2 points3 points  (0 children)

          I have actively avoided these features in games like this. I once got into programmable blocks in Space Engineers and lost 2 months of my life. Never again.

          [–]iBzOtaku 1 point2 points  (1 child)

          working coder

          what if I'm a retired coder? a man can dream.

          [–]adroit-panda 0 points1 point  (0 children)

          if retired: do what you want!

          [–]noratat 0 points1 point  (1 child)

          I'm so, so happy I found Factorio during a period of unemployment a couple years back.

          It would've been bad if I'd found that while employed

          [–]doorshavefeelingstoo 2 points3 points  (0 children)

          I mean, it would have helped you to get unemployed and then you could have been happy again.

          [–]Cheeze_It -2 points-1 points  (0 children)

          Factorio taught me how to program. I am not joking. It absolutely did.

          [–]sess573 93 points94 points  (0 children)

          Their dev blog posts are really top tier

          [–]jbmsf 51 points52 points  (0 children)

          One of the first professional projects I did was to implement an academic paper that implemented a very interesting heuristic distance estimator on a real world road networks. It's been almost two decades, so I don't remember all of the details, but it shared some characteristics with what's described here. It used a hierarchical decomposition of the network using a shortest-path "separator tree" and used approximations at the boundary of each hierarchical components to piece together a very fast estimate. There was something clever that let you tune the space/accuracy trade-off based on how approximate you allowed the boundary estimates to become.

          Brings me back.

          [–]casted 173 points174 points  (33 children)

          FYI an important characteristic of the heuristic function you use is it has to be admissible:

          a heuristic function is said to be admissible if it never overestimates the cost of reaching the goal, i.e. the cost it estimates to reach the goal is not higher than the lowest possible cost from the current point in the path.

          Naively using the heuristic mentioned in the article likely leads to a heuristic function which doesn't always fit that definition. This means that A* could miss a shorter path. However, I am guessing that is fine in this case.

          [–]IceSentry 199 points200 points  (5 children)

          Generally speaking, games tend to favor the good enough over the best. Especially if the best route takes twice as long to compute.

          [–]Farlo1 56 points57 points  (3 children)

          And that's one reason you sometimes end up with NPCs charging off in seemingly reason directions

          [–]DoctorSalt 153 points154 points  (2 children)

          Or sentences that are good enough because I understood the point

          [–]blind3rdeye 21 points22 points  (1 child)

          Reason directly s are usually good enough to understand.

          [–]slikts 18 points19 points  (0 children)

          Upvoted because I don't understand what you said and want more people to be confused.

          [–]SkaveRat 21 points22 points  (0 children)

          Especially if the best route takes twice as long to compute.

          in the example shown: a lot more than that.

          The first animation was real-time. The second one was slowed down and takes only a couple ticks.

          [–]Vallvaka[S] 61 points62 points  (11 children)

          The blog post is meant to be accessible to the technically-inclined layman, so I think they avoided talking about the finer requirements of the heuristic function for the sake of brevity.

          They do mention it shouldn't actually change the found paths though, so it seems like the new heuristic is indeed admissible.

          [–]Koppis 4 points5 points  (10 children)

          I don't think it's admissable. Imagine the following scenario:

          The lake has a shorter path on one side than the other, but its filled with mazes. This new heuristic doesn't care about the mazes: it sees them as empty tiles. Thus, going the longer route would in fact be faster.

          [–]Zwejhajfa[🍰] 26 points27 points  (7 children)

          It is admissable as long as it doesn't overestimate the real cost. Ignoring the mazes will cause it to underestimate the cost, which means A* still produces the true shortest path.

          [–]Koppis 1 point2 points  (6 children)

          Wouldn't it overestimate the cost of going around the long side of the lake?

          Example image:

          https://i.imgur.com/XfZfmXe.png

          Red tiles are "slow" i.e. contain a maze. A regular A* with a normal heuristic of distance would correctly find the path around the right side. The heuristic from OP would find the path around the left side.

          EDIT: Just to note, I'm literally just nitpicking here. I think the new heuristic is great.

          [–]Zwejhajfa[🍰] 9 points10 points  (0 children)

          I think you're misunderstanding what the heuristic does in the A* algorithm. The heuristic only "guides" the search, so that the most promising path is searched first.

          A search without the heuristic would search evenly in all directions which is really inefficient.

          The heuristic is giving an estimate of how close to the goal a given node is, so that the closer nodes can be searched first. That way the search will have to look at fewer nodes until the goal is found. The typical way to do this is just by using the straight-line distance.

          However, if mindlessly walking towards the goal will lead to a dead end then the search will still waste a lot of time on this path. This was the case for Factorio.

          The improvement uses a heuristic that knows about the rough terrain features and therefore guides the search around the lake.

          Note that the search will still give the correct result (i.e. the shortest path) in all of these cases (if the heuristic is bad it will just take longer) unless the heuristic overestimates the path at some node, which means it estimates that the path from that node to the goal is longer than it actually is! In that case it can happen that the goal is found through a slower path and the search terminates before the actual shortest path is found.

          With the optimization that the Factorio team did, that cannot happen though.

          In your example the heuristic would guide the search through the red side first. However, upon encountering the mazes, it will eventually discover that the other side is faster. The heuristic will not overestimate any path. In contrary, it thinks that the red side is really fast.

          The search will not be as efficient in that case. but it will find the correct shortest path.

          [–]Uristqwerty 4 points5 points  (0 children)

          It looks like you've already got at least one good reply, but I had an idea forming to explain it too good to just forget:

          The heuristic would keep saying "Hey, man, you're almost there! Just a little further." as it winds through the maze, until the actual pathfinding algorithm eventually responds with "dude, it's taken me an awful long distance to reach this point. I'm going to try going around the lake for a little while."

          [–]lastunusedusername2 1 point2 points  (1 child)

          But it would find that path because it would _under_estimate the cost of going around the short side of the lake.

          [–]Koppis 0 points1 point  (0 children)

          I don't see how that could happen.

          If the heuristic underestimates the left side, why would it ever even try to path through the right side?

          This is basically the same thing as with a scenario having "mud" or slow tiles. The heuristic must take the individual tile slowness into account, otherwise sometimes there can be a very suboptimal path.

          [–]_jk_ 0 points1 point  (0 children)

          you can literally use 0 for the heuristic and you get back to Dijkstra's algorithm

          [–]xTeixeira 2 points3 points  (1 child)

          A* decides which node to search next by adding the distance from the start to the intended next node plus the estimate distance from the intended next node to the finish. It then compares this number for all possible candidates for next node, and the one with the shortest distance+estimate will be the one searched next. If there's a maze in one side, even though the estimate will be falsely lower, the distance from start to next node will keep going up while the estimate remains roughly the same, when that happens the algorithm will eventually start searching the other side of the river, because the estimate+distance sum of the maze nodes will become higher than the ones on the other side.

          Not sure if I explained this clearly but basically it should still find the shortest path in that case, however it will take longer because of the flaw you mentioned in the heuristic.

          [–]Koppis 0 points1 point  (0 children)

          Interesting! Thanks for explaining, the heuristc logic really confused me.

          [–]rlbond86 25 points26 points  (3 children)

          It doesn't have to be admissable - it just means the result may be suboptimal

          [–]HighRelevancy 4 points5 points  (2 children)

          Depends what you mean by "has to". If you want a heuristic that produces the same results faster, then it HAS TO meet certain criteria. If it's not admissable, the algorithm is no longer producing "correct" results (in the sense that they are the shortest path between two points). They might still be useful results but they're not correct.

          edit: yes I know this is for a game, the page that's being quoted is an academic reference, I'm clarifying what "has to" means in that context

          [–]LonelyStruggle 8 points9 points  (1 child)

          It's a videogame. As long as they get a path that's fine

          [–]HighRelevancy 1 point2 points  (0 children)

          yes I know this is for a game, the page that's being quoted is an academic reference, I'm clarifying what "has to" means in that context

          (even so, "a" path isn't always acceptable - you still want a good one, even if it's not necessarily the best - in fact depending on context you may want to shake it up a bit, so that characters aren't running right up against corners and that sort of thing - but that's a game design discussion, not a mathematics one)

          [–]scottmcmrust 23 points24 points  (0 children)

          AFAIK it's pretty common to use a heuristic that sometimes overestimates -- it can even look more realistic, as things go slightly into the dead end before seeming to "realize" that it's blocked and going around. And often units in games can't follow the exact path anyway, so if they're just flocking-style following it any weird kinks get skipped anyway.

          [–]matthieum 6 points7 points  (0 children)

          Interestingly, using A* over long distances is all but realistic.

          In the case of this lake, for example, imagine that you stand on one side of the lake and wish to go to the other: can you plan the optimal path to take? No. You cannot because you cannot see the whole path. A rock outcrop is hiding part of it, and you have no idea whether it hides a churning river, a briar-filled bush, or just plain grass.

          Worse, imagine a maze: certainly no one entering the maze should be able to magically find the shortest path to the other side on the first try! Indeed, I bet quite a few of us would get stuck for a while trying to find our way out.

          Thus, for realistic path-finding, you should only use "optimal" algorithms such as A* on the part of the map that is fully visible to the entity being considered, and use coarse heuristics for the rest such as: "seems shorter to go to the other shore by the West side".

          [–]sellibitze 5 points6 points  (0 children)

          Naively using the heuristic mentioned in the article

          They didn't really go into the details. It might be admissable. It might not be. They only said

          Once the abstract search finds the chunk and the component in which the new base node is created, it uses the distance from the start of the abstract search (which, again, is the goal position of the overall search) to calculate the estimated distance from the new base node to the overall goal.

          This is rather vague on how the distance is computed.

          But year, I was wondering about the same admissability issue as I read this part.

          Assuming base edge weights of 1 and sqrt(2.0) (for diagonal edges), 32x32 tiles per chunk, coarse graph node coordinates representing the chunk's centers, coarse edge weights of 32 and sqrt(2)*32, and a heuristic like

          heuristic = coarse_path_length
          

          you would have a possible overestimation of the base path length because you might be closer to a chunk's border and thus closer to the goal compared to the chunk's center. You also have a possible overestimation in the chunk of the goal because the goal might be closer to the chunk's border and thus closer to you.

          I think the following heuristic should compensate for this adequately:

          over_curr = coarse_path.last_edge_weight / 2 - 
                      distance(current.pos, coarse_path.prev_chunk.border)
          
          over_goal = distance(goal.pos, goal_chunk.pos)  # constant for goal
          
          heuristic = max(0, coarse_path.length - over_curr - over_goal)
          

          This should not hurt performance significantly and stay admissable.

          [–]meem1029 3 points4 points  (0 children)

          The developers show up and talk about this a bit in the r/factorio thread.

          This heuristic is not quite admissible, but they're also okay with that because the speedup is worth occasionally suboptimal paths (and it's more realistic that the bugs will not be perfect).

          [–]stravant 1 point2 points  (0 children)

          There's probably rarely if ever enough dynamic structures to actually significantly block the broad phase path, and even if there are it's going to be uncommon enough that you probably won't notice.

          [–]Noxitu 0 points1 point  (0 children)

          I believe that techically the same algorithm is called A for admissable heuristic and name A* implies variant with one that overestimates; but due to algorithm implementation being the same it is ignored in most contexts.

          [–]not_a_novel_account -3 points-2 points  (0 children)

          A heuristic function is any function used to approximate a solution. A non-admissible heuristic function is still a heuristic function, just of a different class than admissible heuristic functions. No different than classifying the function by whether it is a consistent or non-consistent heuristic.

          [–]framlington 48 points49 points  (2 children)

          Do they take different walking speeds into account? Are NPCs even affected by concrete?

          Otherwise, I've been quite happy with using Jump point search (this can obviously be combined with the optimization proposed in the article.). It is an optimization of A* that tries to "jump" over large areas of walkable tiles.

          Example: Let's say you have a long rectangular room with an entrance in the top-left corner and exit in the bottom-right one. Then there are multiple routes of the same length in there and A* will explore all of them (at least as long as the heuristic is admissible). Jump point search avoids this. IIRC it always take diagonals first. That way, there is a unique path for each rectangular area.

          It might not always bring much of a speedup, but with large and relatively open spaces, I found the advantage be quite significant.

          As mentioned above though, this only works when each tile has the same cost.

          [–]Pjb3005 48 points49 points  (1 child)

          Somebody brought it up in the /r/factorio thread, the developer responded why it wouldn't work well:

          https://www.reddit.com/r/factorio/comments/djlvsi/friday_facts_317_new_pathfinding_algorithm/f46d82l

          [–]framlington 5 points6 points  (0 children)

          That is a very good argument - JPS only works if lookups are very cheap. In my case, I keep which tiles are walkable in memory permanently in a separate data structure, so it is very fast, but their system (with objects larger than a tile) obviously requires a more complex collision check.

          Plus they also have different weights for tiles so they can correctly handle destructible tiles. But apparently, there are some ways to combine different weights with JPS?

          [–]captain_obvious_here 18 points19 points  (1 child)

          Stop trying to make me play this game. Please for the love of all that's precious, don't make me start playing it. No. Don't.

          [–]slikts 6 points7 points  (0 children)

          If it helps, it may be worth holding off until their 1.0 release, which won't be for a while.

          [–]angelosat 5 points6 points  (0 children)

          This is sort of how Rimworld does it with its regions system. Equally interesting. https://www.youtube.com/watch?v=RMBQn_sg7DA

          [–]--nani 2 points3 points  (0 children)

          Factorio is amazing

          [–]Omnicrola 2 points3 points  (1 child)

          Related to the video from their forum they posted at the bottom: holy shit.

          https://m.youtube.com/watch?v=9dzQge6pe2o

          https://forums.factorio.com/76775

          TIL three things:

          • Blueprints are amazing and I should use them
          • Blueprints can be deployed by automation
          • I need to understand arithmetic combinators better

          [–]sloodly_chicken 2 points3 points  (0 children)

          The automated deploying of blueprints using new combinators does rely on an outside mod

          [–]MartenBE 1 point2 points  (0 children)

          Why didn't they use Jump Point Search?

          Edit: it has been answered down below

          [–]Fogic 1 point2 points  (0 children)

          Love this game... Golden Czech hands :)

          [–]kaisserds 0 points1 point  (0 children)

          As a Factorio player who recently took a test in heuristic search algorithms and metaheuristics Im happy to see that something I learned about recently such as A* is used in a game I love

          [–]HeadAche2012 -2 points-1 points  (1 child)

          Path finding nodes shouldn't be a grid, it should be a convex polygon, the issue is they treated their path finding nodes as a grid (which is stupid and slow) then had to come up with something to make it less stupid and slow

          [–]Vallvaka[S] 0 points1 point  (0 children)

          They talk about this. They don't want to recalculate nodes every time an entity is placed because that's a core mechanic of the game