In part because of .Pete linking to this article, and in part because I just had a craving to play the game, I started writing a program for Final Fantasy Tactics Advance. After most major events in the game you get to place a piece of terrain on the map, gradually arranging the countryside. Certain clusters of terrain types will have buried treasures, and the nicest treasures will be hidden only under certain patterns.
So it's a basic optimizing problem. Given which patterns yield which treasures, how favorable one item is over the other, and a known list of pieces and the array they can be placed in, which is the best possible layout? So I fired up a Scheme interpreter and got to work. My code generates a few thousand random scenarios, rates each by summing the assigned weight values, sorts the scenarios by that rating, and randomly recombines bits of the best 25% and some more random ones into a new set of a few thousand, and does it all over again. The code does exactly what I tried to tell it to do, but after 7 minutes — about 10 iterations at 4000 scenarios each time (experiment found using more scenarios at fewer iterations yields quicker results) — it's only about two-thirds as good as me sitting down for 30 minutes with pen and paper.
It's still a little buggy. I fixed the problem where, for a given set of neighboring terrain I was checking permutations against the list of items and not combinations. Currently I'm counting literal combinations: if you have four mountains, there are three combinations of three you can make, but I think the game might count only that there is at least one set of three neighboring mountains and ignore the remaining combinations (only terrain types matter). I'd have to play for hours to get to a point where I could test it. Also, I just finished figuring out that I need to carry the best trial(s) over each time so that if the random recombining doesn't yield better results I don't go backwards for an iteration. Thanks to the good old A.I. koan about teaching a computer to play tic-tac-toe for that one (if it bugs you, ESR explains the garbage collector koan and garbage collecting). Also, code profiling shows that more time is spent determining which items will be generated and summing the ratings than anything else. I should get a nice speed increase if I sit down for a bit and rework the algorithm.
I'd like to post the code, but I'd have to have a front page post with just screenfulls of code. I'll find some way to post it and link to it here without getting a whole new site.
I recommend:
If you like FFTA, try Fire Emblem: Sealed Sword or, even better, Advance Wars 2 for more of a tactical challenge. Advance Wars 2 more than makes up in challenge and game play for what it lacks in unique units/characters. For more of a traditional RPG, try Golden Sun but feel free to skip the sequel. All these are for Gameboy Advance.
I'd have used the very excellent MacGambit scheme interpreter and IDE, but my Mac only has a 16MHz CPU.
Oh, and I got all my data about how FFTA works from Gamefaqs.
No comments:
Post a Comment