Who am I?
My name is Keith Hanson, I graduated from Rose-Hulman with a degree in Software Engineering in 2021. In my time since graduation I worked extensively with infrastructure as code and on backend systems. Notably what you won’t find in my project background is anything to do with AI. I took 1 course on AI in college, but that definitely wouldn’t prepare me for this project. Speaking of this project, what on earth am I trying to do. My goal is to create a system for determining the “best” possible Factorio factories given a set of constraints. Beyond that loose end product definition I have a few other goals, learn more about AI optimization methods, and to bring you along on my journey.
What is this project?
Firstly, a disclaimer, AI is a hot topic, but this particular project will not be dealing with the likes of OpenAI or any other LLM. AI optimization is actually a fairly different field, based a lot more in human logic. No black boxes of mystery here, as I work through this I should be able to explain every step of the way. If you don’t know about Factorio, just know it’s a logistics game that eats time like Warhammer40k eats money. The goal of Factorio is to automate the building of various resources as much as possible. The process increases in complexity over time with more parts needed and whatnot. So in the infinite desire to have the best Factorio save file, I figured it would be good to write some code to do it for me.
*Example Factory from Factorio*
“Best” is going to be by minimizing the footprint of the factory, and minimizing the total resources required. While still achieving the required output of course. Multi objective optimization is a classic use for AI, and as such I expect that I will be covering little novel ground (an important thing when you are learning something new). Unfortunately I am also going to be new to Factorio and to modding, so we have a lot to learn.
What I’m trying to do
So, firstly, what I’m not doing. In factorio there is of course a non-trivial amount of yak shaving that goes into any desired output. If I want an inserter I need an electronic circuit, an iron plate, and an iron gear. An electronic circuit takes 3 copper cable, and 1 iron plate. Copper cable is made from Copper plates. Copper plates and Iron plates are made from Copper and Iron ore respectively. All of these things have varying rates that they are needed at which makes a difficult optimization problem on its own. Luckily someone else already did that leg work and made a python library for it. So I’m not going to be coming up with the “material list” of needed building to optimally make a particular output at a particular rate given certain inputs.
Instead I focus on the geometric layout of those pieces so that all requirements are met. For context, making electronic circuits takes 2 machines. Or 15 if you want to do 6 of them per second. Because each layout has to have a continuous flow of resources we can think of it like solving a maze, but instead of having 4 different directions we can head in, we have inserters and belts that can each be places in 4 orientations, and assemblers (any of them from the pre-determined list) that can be placed in any of the bordering tiles. So it becomes increasingly important to search smartly, hence AI. The algorithm A* is going to be the cornerstone of solving this problem.
What is A*
The most basic answer to A* is that it is an algorithm for solving “mazes” where you give a combined metric of how “expensive” a path is, and your best guess at how much longer till it reaches the end of the maze, using those 2 metrics it ranks ALL possible next steps from what was just checked, and throws it onto a pile in order, excluding the ones that have already been checked, or thrown on the pile. Then it checks the next best score, sometimes this will be a child of what you just checked, sometimes it won’t. There are some great visualization tools for how the algorithm works through solving a maze. The one below is getting from the start point on the left to the end point on the right, with the colored squares being the explored region
A* but complicated
The basics of A* lean on “give me an objective number on how good this is” and says “I’ll check in order of how good they are”. But how do you put a number to how good a particular solution (or partial solution) is. The answer to that is… it depends. So what I’m choosing to go with is based on a library in python called MCDM which stands for Multi Criteria Decision Making. It has various algorithms it supports, and by the end of this I expect I will be familiar with most if not all of them. What each of them does however is return a ranking, with a single number, of each of the input vectors. (math term for list of numbers, in my case, [“effectiveness”, “cost”, “footprint”]).
Before we begin
One of the first things to do is pick a coding language, one of which has already been chosen for us. Lua is the language you write Factorio mods in. But that doesn’t have to be the language used for writing out the algorithm. (the downside being that you would need a separate program running alongside Factorio, or that I’d need to re-write the algorithm in order to integrate it into a single Lua file). Lua does not have the support I needed for this project, so I went with python for the algorithm. This is to get into the meat of the AI portion of the problem sooner. It makes the mod support much uglier, but as with all great mistakes, that’s a problem for future me.
Optimizing
This is a problem that, if I’m not careful, can be INCREDIBLY non-performant. But, after spending a lot of time early on worrying about performance and not having anything working, I decided it was smarter to get it working first, then make it faster/find a way that is faster.
Future Updates
The goal for updates going forward is to highlight things done, or lessons learned. The next one will center on modeling Factorio in python, then we can get into more of the AI stuff.
Estimate
My naive breakdown of the parts of this project are as follows: (I will be keeping a rough time investment on each segment, figure it will be fun to see how it compares to my hours in Factorio)
- pre-planning: 16 hrs
- blog writing: 10 hrs
- basic familiarity with the game: 8 hrs
- after 12 hours of looking into tools and reviewing academic papers, I figured it was a good idea to actually buy and play Factorio for a little bit. (This was a mistake)
- import info from game: Unstarted
- export result: Unstarted
- state-space model: 16 hrs
- pick multi-objective search algorithm: 6 hrs+4 hours for implementation
- expand scope: Unstarted
- “Dead end” research: 24 hours
- Optimize Search and Debug issues: 24 hours
We will see how well that section ages.
The Big False Start
So, I went on a big rabbit hole of terminology. There is significant math terminology around AI and optimization when you start in the field. And so I went back to school for a few days, only to find out that what I was reviewing doesn’t apply to the problem I was trying to solve. Essentially I was looking extensively into single criteria decision making, woops. There is some potential for me to apply that information later, but I highly doubt it. The topics I was studying were based around this page. The associated lecture quickly started to reference partial derivatives, which I remembered vaguely from school, but needed to brush up on to avoid getting lost. After spending a bunch of time getting re-acquainted with the relevant calculus (partial derivatives are theoretically not that spooky, but they use a lot of special characters, so it can be hard to keep up when you are rusty). I got pulled into a few different rabbit holes based on the Oxford course lectures because I had a hazy memory of learning it back in college, and the terminology seemed like it should apply, but ultimately it wasn’t related to what I was looking at. Ultimately the end of that rabbit hole highlighted that Lua’s Torch package is not what I was looking for for supporting my project. Solidifying that Python was going to be the language I wanted to work in.
