Sonstiges: Developer Diary - The Creation of a Switch Game
Michael Grönert, am 26.12.2016, Seite 19 von 25
BadToxic Discord Server | GameMaster Discord Server | BadToxic on Twitter
BadToxic on Instagram | BadToxic's Dev Instagram | BadToxic on YouTube
Part 19: Porting Fizhy over to GameMaster & AI
Last time, we completed the new mini game Fizhy Zen, which is available in the Google Play Store for Android and Apple App Store for iOS as a standalone game. Today we want to port it over to our main project GameMaster as a third mini game.
The usual tasks when porting
This time I created a kind of tutorial for the steps that are always needed when I want to add a new game. I hope to be able to further optimize the process to be done with it even faster in the future. After copying the files from the Fizhy project to the GameMaster project, there is much to do. I'm introducing a new game cartridge to start Fizhy via GameGuy as well as a quick start reference to shorten the process of testing the mini game. Hard coded texts must now be moved out to the translation files to read them from there. References have to be distributed to different objects so that they can find the corresponding information. For example, the GameGuy console needs to know which object to instantiate in order to start the game. All in all, a lot of small tasks that aren’t a lot of fun. A large portion of it is necessary before the new game can even be started. Additional tasks such as creating a skill tree, achievements and options, or enabling savegames and (online) multiplayer should only be considered once the game has been successfully integrated.
Unfortunately, I did not think ahead enough in one point. Fizhy Zen is not designed for the kind of multiplayer I would like to implement. The problem is the structure of the objects: playing area, fish, baits, fishing rod, etc. are not subordinate to the player, but to the game itself. In other words, it is not possible to have one playing field per player without major restructuring in the code. An easier solution would be to implement a kind of co-op game in which two players at the same time fishing on one pitch but that’s not the way I imagined this and thus I have to bite the bullet and do much refactoring.
An artificial intelligence
Compared to the two existing mini games, AI is a huge challenge in this game. Rarely do I fall back directly on theoretical knowledge I acquired at University but here I lack practical experience. Terms like "backtracking", "breadth-first search" and "depth-first search" as well as associated processes come to mind immediately. Perhaps the most exciting topic that I have faced with this project so far. However, there is a lot of planning and thinking to do before taking too many steps in the wrong direction. An ideal solution does not exist here, as long as one is subject to the usual natural constraints, such as limited storage and runtime. An AI could perfectly play with a database with optimal moves for every possible situation. I have to drop this option, however, because even if the storage needed would be less of a problem these days, I might need years to create something like that manually. It’s like with chess - you can not always try all the following moves to determine the best course of action. Usually a combination of a search algorithm and a database of important moves is used instead.
I'll start by preparing a recursive search algorithm: A function that will test all reachable fields for each bait thrown in. In a given order, it tests each possible bait move in turn. You can tell whether it goes to the left or to the right first, i.e. along the breadth (Breadth-first search) or down in depth (Depth-first search). So the AI walks "paths" in the game area. However, it doesn’t do that in the visible game area but in an internal data structure which is a representation of it. A test function will be performed on any field where a bait can lock because of a fish, other bait, or ground beneath it. This test is designed to determine how good or bad the position is and rates it with a score. Whenever the bait runs into a dead end, meaning it has no other direction to move to available, it goes back to the previous field and from there use the next remaining free direction. This is called backtracking, in this case recursive backtracking. Each field that has already been traversed is also marked so that you do not visit it again, starting from another field. At the end, the path that leads to the position with the highest score is selected. For each test, the current path is saved if it has outbid the highest score so far.
For reference I can print out the paths of the search while testing.
The evaluation function
So our search algorithm tries to evaluate different solutions without considering the consequences of their actions. A common approach would be to use the same points for evaluation the player would get. For Fizhy that would be the score for catching fish. It’s obvious this is not enough in this case - it usually takes a few moves in advance to catch fish. In addition, it is not always the best strategy to catch many fish as fast as possible because you could obstruct other fish. In addition, I have decided to observe the current turn only and not to calculate any following turns. After all, you can see the next three baits, so it would be fair. But first I want to avoid that too long computational processes could cause problems, especially on weaker devices.
So there it is, the biggest challenge in this project so far - the evaluation function for testing the positions. Starting from the position to be tested, we look for both bait parts in all four directions to see what bait and fish there are. Simply put, we want to count how many same-colored and different-colored objects are next to us and give more points for the same color and less or even negative for another color. But that is easier said than done. On the one hand, empty fields between the bait and the surrounding objects should play a role. They should influence the evaluation to the extent that the bait is placed closer to the relevant objects. So we weigh the points in proportion to the distance of the objects to the current field. On the other hand, objects of the same color behind a different-colored object should no longer, or not very much, contribute to the evaluation since they can not form a direct line with the bait. We also do not have to look endlessly in all directions, just to the edge of the game area or a certain distance. For example, four or more objects of the same color would dissolve immediately, so you only have to look in all directions up to a distance of three or four. A special case are objects above the current field: baits may already dissolve when stacking before the object is reached. In addition, care must be taken that there is enough room to accommodate other bait parts to complete the chain. Accordingly, one would also have to look in the opposite direction again, whether there are already same colored objects or there is still room. Of course, the other bait part must also be taken into consideration which at the time of the test is not yet part of the game area. In addition, you can easily block the throw-in area in the middle of the pond. Therefore, you should again give a negative rating depending on the distance to the point of entry.
As you can see, there are countless little special cases that make implementation difficult. And even if everything is considered, it takes a long time to experiment and observe the scores to find good values. Here are some basic example values:
Points for the same colored fish: 200
Points for the same colored bait: 30
Points for different colored fish: -150
Points for different colored bait: -40
Something can be resolved: 350
Not enough space to complete the chain: -50
Once all these things have been implemented, there are other special cases. For example, a fish that is high up and does not have enough space from above to be caught. As already mentioned, this can mean that it can not be reached from below because a similar colored stack would dissolve in advance. Therefore the rule is needed to prefer other colors in this case. For that to work you have to check more fields up than down or to the side. Another observation shows that it is difficult for the AI to get at obstructed fish if dissolving other bait parts in another location also gives as many points as clearing them around the fish. So again we need a rule that states parts close to fishes should be resolved preferentially. This topic in itself is already a complex problem. Strictly speaking, for each field you have to know how many fish there are and weigh them in relation to their distance. This value can then be added to the rating. However, it is not easy to find a good median so that the desired area is indeed preferred but not exclusively played.
Here you can see the weights of the fields depending on their proximity to the fish.
The AI is still far from playing perfectly - but it does not have to, you still want to be able to win. However, I'm afraid that it does not play well enough to be a challenge for an advanced player. Nevertheless, I have to go forward and not spend too much time with it, even if I do not like leaving things unfinished.
Since the AI development has already taken so much time, I postpone the implementation of online multiplayer for now. However, I still want to implement a local multiplayer right away. As mentioned at the beginning of this diary entry, this requires a major restructuring of the code. All instances belonging to a particular player must be subordinated to it rather than the game itself. Needless to say, the mechanics also have to be adjusted. For example, it must be decided when a game is over. If we have four players and one has finished his level, is the game over for everyone or can the others still fight for the second, third and fourth place? Another big change is that players can play different levels. So we need another menu before the start which allows this to be set for all players.
Each player can start in a different level.
In addition, depending on the number of players, the positions of the playing fields and the UI texts have to be adjusted. Especially if we want to support different screen sizes and aspect ratios, this can be a challenge. Not to mention that I still support the 3DS resolution and there is not much space on such a small screen.
Four players on a 3DS screen - there is still much to optimize.
Skills and Achievements
Last but not least, I would like to briefly discuss the other topics mentioned above. Even Fizhy gets a skill tree. As usual, we offer learning different AI difficulty levels. Added to this is the graphical enhancement of 2D sprites to three-dimensional models and the already shown local multiplayer for up to four players.
These skills are offered so far.
Once the 3D fish are learned, they can be activated and deactivated in the options menu at any time. While I’m at it, I also implement several achievements. Partially I can reuse graphics from the old Fizhy version here. You can unlock these achievements by catching fish, dissolving lures, making combos, winning games and finally collecting all the achievements.
A few simple graphics for the Fizhy achievements
With that I would like to conclude today's diary entry - that was a lot of text, after all. And yet I only manage to scratch the surface of the topics here and skip a lot of aspects. Next time, I want to talk about the community that should be behind such a project. It is essential in many ways. In addition to the society of like-minded people, further aspects are in the foreground, from pure information finding over support to marketing.
Do you prefer to read this diary in the developer's mother tongue? Then click here to read this diary entry in the original German language!