freeserf
freeserf copied to clipboard
freeserf
AI decision flowchart
I've created a flowchart that represents an AI player decision tree that I believe will create a decent AI opponent. I'm going to start trying to implement in code.
freeserf_ai_flowchart.pdf
freeserf_ai_flowchart_draft.zip
I forgot to include sending geologists. I think that would be under housekeeping tasks... send a geologist to and areas of mountains where few resource flags placed, few geologists active
I've started implementing this. I realized along the way that my map-searching logic isn't looking in the locations I intend, and it isn't obvious why. To help develop this I am now trying to create a new viewport layer to overlay AI search, similar to the debug overlays triggered by the "g" key. Being able to view the resource gathering and expansion logic in realtime in-game will be helpful for developing an effective AI.
In fact, AI player acts exactly the same way as a live player, i.e. he moves the cursor (accidentally pokes at the map until he enters his territory if he already has a lock), then he concludes that he can build in this place and is this really needed at the moment. This approach works because AI player does this much more often than alive.
The code for finding out the possibility of construction is already there, for the evaluation of resources when building a castle is the same. For the construction of a lumberjack, a stonecutter, you can estimate the amount of forest / stone around (I can roughly say how to do it properly using existing possibilities). For the construction of mines need to send geologists and intercept the events of finding the ore.
I want to finish this release (0.3) and deal with the extraction of a separate entity - a PlayerController that will have several implementations - a local player, an AI player, a network player.
I am trying to use as much of the existing code as possible. Because I have little object-oriented programming experience I am struggling with passing variables around. During my initial testing I put my AI code in the interface.cc and triggered the AI actions from a keypress. The logic I was using for the first phase (building sawmill, 2x lumberjacks, stonecutter, 2x knight huts) is this:
- locate AI player's castle (re-using same logic in existing codebase)
- identify six "corner" points four tiles out from castle - south, southeast, northeast, north, northwest, southwest ( new logic I wrote, I hardcoded offsets from centerpoint for each corner)
- count trees and stones within three tiles of each corner (check each map pos from add_spirally and check for Tree0 though Tree7, Stone0 through Stone7)
- starting from corner with most trees, try to place a sawmill (add_spirally from corner pos until can_build_large is true)
- connect sawmill to castle (copied road building logic from the "double-click to autocomplete road" code. Flag position for a given building is always the same offset from building pos, 6 I think)
- place two lumberjacks near corner with most trees (spiral outward from corner pos until can_build_small is true)
- connect lumberjacks to sawmill
- place a stonecutter near corner with most stones, connect to sawmill (same logic as wood placement, except I'm counting the number of stones per pile to determine the richest area)
- build two soldier huts as far from castle as possible, connect huts to castle (pick two opposite corners and spiral outwards and create a list of MapPos where can_build_small && can_build_military true, then try building at the point farthest from castle
Do you and jonls have knowledge of the actual game code? Or are you trying to reverse engineer it based on how the game plays? I cannot tell how the original game AI works. It seems quite primitive, and the character personalities don't behave much differently.
I would like to see Freeserf be a true copy of the original, and then I would like to create an Enhanced version, perhaps with extra features as options with the original game as the default mode. I am working on the AI first because I play this game often enough that the poor AI is the biggest annoyance.
If you would be so kind, please let me know your plans for AI development. If you have no plans to create any AI I will write one and submit my code as-is. If you plan to re-implement the original game AI I will still write my own alternate AI, and then attempt to implement my logic in the new PlayerCharacter class you describe.
I fully share your vision of the game :)
We may go from two sides - to realize your AI and at the same time clarify unclear things with the original code.
After looking over the code I believe I've found a good place to hook the AI in. When mission.cc's GameObject::instantiate function is called, after each player->init_view I can test the player->is_ai() result and create an AI object for AI players. I have a new AI class that stores the AI logic and some small variables the AI uses to store data, though it is mostly stateless and shouldn't require being written to savegames.
I have the map overlay working so I can put colored dots on spaces that the AI is analyzing. However, I want to slow down the AI so I can watch as it analyzes tiles. Slowing it down is more complex than I initially thought it would be - because the game is single threaded I cannot simply "wait" inside the AI code for some ticks/milliseconds as the whole game would pause. I am thinking perhaps I can move the AI loop call into a thread so it can run at a pace slower than the rest of the game. I am playing with this now.
I got threading to work. I can manually kick off AI action loops that run in background. Now I can change the AI pace without having to constantly hook in to the game update functions. Not sure if I will run into issues with the threads, we will see.
Now that I have the ai overlay and threading working I can debug my AI logic. What prompted me to do this is that positions I thought to be North, South, etc. were clearly not correct. I can now easily fix this. Also, this made me notice that I'm only matching deciduous trees, and not pine trees, when counting loggable trees.
Hey guys. I ported the game to C# and also started to implement the AI. I use a flexible chain of AI states with an idle state that stays at the base and will trigger other states from time to time. Most important states were to decide to build new buildings and where to build them. I added some search methods to the map to do so easily. Rest of the states deal with linking flags, change player settings, craft specific tools or choosing a good castle location. I am not finished yet but it already works quite okay in the beginning. I also added some values like "aggressivity" or "foodFocus" that depend on the character and I also included the intelligence for decision making and timing. I guess in the end the time-consuming part is testing and fine-tuning. You can find the project here: https://github.com/Pyrdacor/freeserf.net
Very nice, Pyrdacor! I just looked at your AI and AI states code. It looks quite complete, especially with character personalities already implemented. I thought about state-machine design but I wasn't sure if it the states would be straightforward enough. I am starting with a rules-based design because it matches the way I personally play the game, so it is easy to translate my play approach into code.
One thought I was to have the AI fork its own copies of the game and accelerate them to predict the result of various actions, like a chess AI. This is probably very excessive for a game as simple as Serf City, though. I suspect there is really only one optimal strategy.
I think the main problem for an AI is decision making. This is easy for a human player but very hard for an AI. The decision making in my system is mostly based on map information, game time, personality values and RNG and is not really bound to the state machine approach. The state machine is basically exchangeable and doesn't do really much. The main work is done inside the states and most of the work is only done in a few of them. Beside some special cases (like low supply start) I see the main problem in deciding when and where to build buildings. To allow intelligent decisions there must be enough information about the game (and especially the map). This is the reason why I added some functionality like "find in area around x", "count in area around x" or "get spot near x".
I am not satisfied with my current AI implementation though. If I want to handle a whole game, some AI states will become code monsters as long as I won't find clever conditions that scale well till late game.
As I looked at your chart I remembered a huge problem I still have with my AI. You wrote "expand borders towards borders". This towards is my problem. To find an area with some properties is easy but when I want to find a spot on the map that is inside that area and in a specific location relation to something else, it becomes a bit complex. If you have a handy algorithm to quickly calculate the "towards" property or some ideas about it, I would be glad if you could share it.
I do not have any such algorithm though I suspect it must be a common enough programming need that one can be found online. My naive approach is to divide the map into chunks maybe 9x9 tiles and calculate the resources inside each chunk, then use the existing path finding code in free serf to plot towards the center of that chunk, then try to build a hut near where the desired path exits the players borders. You would have to modify the pathfinder to avoid masses of tiles where huts cannot be built when plotting a course to a distant target
One challenge will be building efficient roads to transport resources. An annoying limitation I believe exists in the original game and freeserf is that destroying flags/roads in the plotted path of some resource being transported by serfs results in the order being cancelled, which is hugely inefficient and discourages ever destroying roads. It seems to me that an “in-flight” resource’s route should be re-evaluated at every flag but that would change the original game behavior and so I would want it to be an option instead of default.
I also have some ideas to improve the game that would change the game too much. My plan is to add some kind of mod support and add a first mod which exactly contains these changes. The best roads are indeed not easy to find. I now use the closest flag and repeatly check that everything is linked to a castle or stock. But this does not mean that the transportation routes are efficient. At the moment it works quite well but testing late game AI is a very time-consuming task which I couldn't achieve until today. Yesterday I improved the behavior with minimum starting supplies which was also very bad in original game. I'm quite satisfied. The AI will often succeed in building a food source and a coal and iron mine.
I am realizing that because none of my AI functions require any persistent state I should make my AI class entirely static. I am refactoring it as I keep finding simpler ways to do things, especially re-using existing functions that I didn't realize existed.
For example, flag->can_demolish means flag is disconnected, so I can use that to find disconnected flags. Also the pathfinder calculates road lengths so my "connect disconnected flags" function is very short, it gets all flags, if owned by player and can_demolish then use pathfinder to buld potential roads to all other flags, compare length, pick shortest one. I thought I'd have to write more code for this but it,s all there.
I would not recommend to use functions of different purpose for such things. Moreover can_demolish checks things you don't need to check. You should split can_demolish and use only the required part. You can also look at my code. The linking of disconnected flags is already there and similar to your description.
Yeah I just noticed that can_demolish requires there be no connected building (which makes sense) so I'll just write a "is_connected" function that does that part.
I updated the ai overlay to draw pathfinding logic as it builds potential road solutions so I can better understand pathfinding decisions and implement more complex road building.
Is there any function to count the "flag distance" between flag MapPos? All functions related to finding resource targets appear to ultimately use FlagSearch::execute which appears to return the first result that meets the callback criteria (ex flag->accepts_inventory if looking for a place to store resource) but I don't see any way to count the flag distance to use for comparing potential roads. The FlagSearch code is difficult for me to understand but it seems to check all dirs for flags connected to the start flag, and follow each dir repeating this process until one of the flags meets the callback test. I believe I could create a modified FlagSearch::execute that returns the flag distance, but because it is called through a chain of other calls it would require creating alternate copies of those functions also. It is doable but I wonder if there is a simpler way I am missing.
It seems like the flag distance be equal to iterator of the FlagSearch::execute loop. I copied the functions to return that number instead of a bool.
If you mean the distance as "count of road segments" you can use Road::get_length. This of course will only give you the road length between two directly connected flags. If you want the distance in tiles you can use Map::dist_x and Map::dist_y.
The only way to build roads is the pathfinder and the building road in the interface. So if you need more information about a road this might be the places you want to add them. In my case I wanted the cost of a road (which the pathfinder uses to determine the best one). Therefore I added a property Cost to the Road class which is set by the pathfinder and when building the road with the interface.
To get the total cost between two arbitrary flags I will implement another pathfinder which will only consider flags. My Cost property will be the input for this new pathfinder. But this is only one idea to do this.
Didn't see your last comment. So flag distance means amount of flags along the path?