Home
One-A-Day 3: Galcon in Python
26 March 02021
I decided to make a python version of the game Galcon, which is a casual RTS game about capturing planets, which automatically create units that can be sent to capture more planets. Graph theory is one of my favorite areas of math, and looking back on my time studying it most of the graphs in question were static. One of the things I want to explore more is what happens when graphs change over time. Say for example you have a solution (either exact or approximate) to the travelling salesman problem. If you add one point to that graph is there a way to use your previous computation to get a solution to the new graph, or do you have to throw it out and start all over again? And if you can reuse your computation, is there a risk of creating some sort of path dependence where the order of the points you add can lead to poor solutions.
Anyway, the code for this project wasn't too difficult, most of the code is just dealing with the game logic of resolving moves. Most of the trouble I had was with the algorithms to decide which moves each player makes, specifically the attack_weakest_neighbor function, and that was mostly down to the number of variables I had running around.
Things to do if I had more time:
- One or two more move-deciding algorithms, specifically one that attacks the weakest neighbor only if they can capture it
- Do a bunch of tests to see what kinds of maps lead to draws and for which algorithms.
- Making a minimax algorithm or throwing some machine learning for a move-deciding algorithm
Lessons learned:
- If you're trying to do a bunch of filtering and sorting and what not with two or more lists, be very careful when you use the .index() method on the original list. If you have some filtered version of a list, and the original list has repeated values and one of those values is in the filtered list you may get the index of a value in the original list that you filtered out.
- Purely random algorithms are absolute garbage for game playing and can be beaten by the simpleist algorithms
- Sprinkling in some functional programming to traditional object oriented can do a world of good.
Future ideas:
- I'd be interested in trying to write a min-max algorithm for this. I know it's sort of the same project, but it's my blog so I can do what I want.
- Play around with the traveling salesman problem and its various approximations.
I'm going camping over the weekend, so one-a-days will be paused until Monday.
