GameDevTV Jam 2023 Planning

 It has been a while since I have posted something here, but now that I have a tiny bit of time, I can finally work on my own things, so am entering the GameDevTV jam for this year. Why? Everyone who enters gets a free course so why not? I am going to be focusing my free time on writing some books on creating a game engine from scratch, so in preparation for the game jam I will spend the days I am able to work on it creating a game from scratch. Unfortunately, I still do have other obligations so will only be able to get in 30-50 hours during the 10 days so will have to take that into account. I am losing this first weekend and next Friday for sure and suspect there will be interruptions on other days so we will see how much I am able to do.

What do I mean by from scratch? There will be no libraries or frameworks other than the standard libraries and what DOM provides. I will write all the code. Ideally,I will extend this restriction to artwork and sound effects but that will depend on how much time I have at the end for polishing the game.

The theme of the game is Life in 2 Dimensions. The thoughtI immediately came up with is some variation on Conway’s Game of Life (CGL). Doing a straight CGL would not be much of a challenge, but if I did this more like a strategy game then there could be something interesting.

My idea is to use a hex grid where there would be 3 distinct types of cells which are either food or enemies. Red Cells eat Green cells which eat Blue cells which eat Red cells. Each round is broken into phases. Phase 1 would be the absorption phase where the cells around each cell is counted. If there are more enemy cells touching a cell then allies, the cell will be absorbed becoming an enemy cell otherwise it stays the same. The next phase is the movement phase.  

The rules for movement are easy. Head towards the nearest food cell (or, fake food cell when I add that later) though only using empty cells, so will stay still if cells closer to food are currently blocked.  Not sure what order the cells will move in, will be playing around with that aspect. 

The game will be an attempt to convert the entire board to your color. With the ability to place fake food on the board to guide the activity. I am hoping to have a crude version of the game by Tuesday or Wednesday as due to other obligations I am not going to be able to start until Monday. 

The fullscreen API

With my masters degree finally complete, I should have a bit more time to focus on my site. Unfortunately, my Dad is now disabled so I am taking care of him and being a care-taker has been taking far more time than anticipated. As he slowly improves, the amount of time I have available to work on my own things is slowly increasing but this may change shortly depending on upcoming events which I will talk about if they come to pass.  Reworking my site is certainly something that needs to be done. One of the big issues that I have is the size to make my games.

The problem is that there is no way of knowing what resolution that the user of a web application is using. The image below shows the different common resolutions that have been used in the past to the present. Making this problem more awkward is that windows don’t need to be full screen and different browsers have different amounts of stuff surrounding the page contents.

 

My plan was to use a 16x9 aspect resolution for future games as that has become the standard screen size. With most modern machines having at least 1280x720 resolution so 1024x576 seemed like an okay resolution to use for future games and I have been playing around with this. On my desktop machine, which was HD, this looked okay but when my monitor was upgraded to a 4k monitor, the locked resolution problem became exceedingly apparent. 

Two viable solutions came to my mind. The first is full screen mode that I have seen other sites take advantage of for videos. Looking into this, I discovered the fullscreen API and decided to explore this with my Canada Day game that I released on Canada Day (July 1st for the non-Canadian’s reading this). The API is easy to use once you have figured out how to use it, but as is often the case it does have a few weird aspects to it.

The API is invoked on a HTML display element which becomes full screen if the browser supports this. This is simply done by calling the element’s requestFullscreen method. This is simple enough but exiting full screen is not done by calling the element’s exitFullscreen method as any reasonable person would expect. Instead, you need to tell the document that you wish to exit full screen mode. While I can sort of see the logic behind this, as the element is becoming full screen and the document is returning from full screen, but couldn’t elements have an exitFullscreen method that calls the document version? API design really needs to be improved in this industry.

Once you are full screen, the next issue crops up. The canvas is the wrong resolution so it needs to be adjusted. This is assuming that you were even successful at switching to full screen. There is a “fullscreenchange” event that is triggered by switching between full and regular modes so writing a handler for the switch is easy enough. Finding the resolution for the full screen can then be done by using the screen.width and screen.height read-only variables.

function toggleFullscreen() {
    let canvas = document.getElementById("game");
    if (document.fullscreenElement == null) {
        canvas.requestFullscreen();
    }  else {
        document.exitFullscreen();
    }
    draw();
 }
function fullscreenChangedHandler(event) {
    let canvas = document.getElementById("game");
    if (document.fullscreenElement != null) {
        canvas.width = screen.width;
        canvas.height = screen.height;
    } else {
        canvas.width = 1024;
        canvas.height = 576;
    }
    canvasRect.w = canvas.width;
    canvasRect.h = canvas.height;
}

The game can then be developed in 4K and scaled to the resolution of the display. My thoughts are 4K will be good for a while so will use that as a baseline resolution for my future development. Scaling to lower resolutions may not be the best approach but works good enough for now. Ideally having different images for different resolutions would be the better solution but it may be quite a while before I bother working on my LOD system and I will likely switch from canvas 2d to webGLx before doing so.

Locking the canvas size in the non-fullscreen mode is the next challenge. I am thinking that the canvas should scale based on the canvas size so next month’s game will be experimenting with that.  

Death of the Phoenix Postmortem

 On itch.io, I noticed that gamedev.tv was having a game jam where all entrants got a free course. I decided to enter but have noticed a very unfriendly opening advertisement when I go to the gamedev site so am a bit leery.  The game I quickly wrote is on Spelchan.com and is called Death of the Phoenix as the theme of the jam was “Death is only the beginning” so this matched the theme. Here is my postmortem of that effort.

What went wrong

One of the most important aspects of a game jam is that due to the limited amount of time you need to have a realistic plan. The best approach is to start off with a basic game then, once it is working, add features until the time runs out. With a theoretical 10 days, it was easy to have a more ambitious plan. Unfortunately, I am taking care of my father who recently had a stroke and ended up partially paralyzed. With my caregiving responsibilities, the amount of time available to me is limited so a day is only a few hours and ended up being even less. 

My original plan was to have a map that the player would need to explore to find the material for building the nest and the location of the nest. The story would be told as brief cut frames that would happen when certain tiles were traversed, and there would be areas where the player would be able to restore their health that would act as save points if the player died.

When it became clear that the amount of working time was less than anticipated, my plans needed to be changed. I had implemented the combat system so decided to drop the map and simply have a visual novel instead. 

What went right

My original story system would have a class that would use a JSON object to provide the layout information for the scene. I had hopes that there was spare time left I could add animation parameters to the JSON data and have animated cut scenes. The JSON data format is a simplified version of class definitions in JavaScript making it extremely easy to use as objects. Because it is a human editable format, it is easy to create by hand. This makes putting together a script very quick and does not require code be written. I was even able to use the room scripts for the title screen and losing screen making a very quick visual novel language.

I want to expand this into a proper adventure game engine so will be experimenting with using JSON as a script (or collection of scripts) for some of my adventure game ports that I am planning to do. The data-driven approach makes some sense, and when combined with a command pattern may make for a straightforward way of quickly building episodes for a multiple episode adventure game but don’t want to go into details until I have something concrete. 

Mixed blessings

 My original intention was to do all the artwork myself but for prototyping I made the fortuitous decision to use creative common and public domain artwork as my placeholder art. This had the advantage that if I did run out of time, the art already is there, and I simply need to add attribution text to the game page. The downside is that mixing assorted styles of art makes the scenes less seamless. This can be fine in different regions of the game but can still be jarring. This is a worthwhile tradeoff as having a releasable build, even if not as polished as desired, is a good safety net.

Temporary artwork does need to be from a source that you can use, which reduces the source material, but does not need to be public domain or creative commons. Having royalty free assets would also work for temporary artwork. I have bought several bundles of royalty free music and art so simply need to go through the libraries I have and start using them.

Future plans

While I don’t expect to do anything with this game, I will be experimenting with building an adventure game engine using some of the approaches used in this game. I'm not sure how quickly this will be done as my time for work is limited, but an adventure game engine which is general enough for other games would allow for several of my larger projects to be completed quicker, so is a good direction to go.

Making Santa-Tac-Toe part 4 of 4

Part 4: Building the GUI

 In the previous parts, we created the core game logic and the AI agents that play the game. This was probably the most difficult part of this project, and we would not have a game without this work. Unfortunately, the part of the project that users care about is the user interface as this is what they see. User interface code tends to be bulky but simple so for this chapter we are just going to summarize what the classes that make up the user interface do and how they work together. For those readers are interested in detailed code, the source code is located at https://github.com/BillySpelchan/BlazingPorts.

As is common, the graphics for the game are all combined into an image file known as an image atlas. A scaled down version of the atlas image is shown below. As can be seen, all of the screens and the messages are images for this game to make things really quick. The downside to this approach opposed to programmatically building the display from simpler pieces is that the images are much larger and use up more space. For this simple game, the costs of a longer image loading time is more than offset by the improved performance and simplicity in coding.

All the image bounds and positioning information is stored in an object called STTConsts. Using an object to hold all the games constants keeps tuning information all in one area, making for an easy way to configure things.  In addition to placement information, the config also holds button configuration, enumerations, and AI settings for the two different opponents. A more general configuration file would probably want to avoid non-JSON data types for security and maintainability reasons.

Our game is screen based, with the STTMain class handling switching and controlling the screens. Having all screens controlled by a common host has the added, but not utilized here, advantage of being able to share messages and state information between screens. Screens used in the game share a common class creatively named Screen. This class has two utility methods to ease the UI requirements of the game. The createButton(label, bounds) method creates and adds a button to the display list. Likewise, createImage(atlasEntry, position=null) retrieves an image from the image atlas and displays it at the specified location.

The LoadingScreen class is the initial screen that is shown. loading screen only one which doesn’t use images from the atlas but instead displays a loading message until image atlas has been loaded. Once the image atlas has been loaded, the TitleScreen class is used to display the title. It has buttons to switch to the InstructionsScreen or one of two instances of the SelectScreen class. The InstructionsScreen simply displays three images that make up the instructions.

The SelectScreen has parameters for setting the background image and labels to allow both Santa and Krampus to present level options to the player. This determines which AI and which instance of the GameScreen will be called.

As with the SelectScreen, the GameScreen has configurable images so Santa and Krampus have their own screens. The game screen uses the STTTile class which uses images of Santa for X and Krampus for O which are displayed in the board. Game state messages are displayed as a comic-book dialog bubble at the top of the screen. Finally, the PlayAgainPrompt class is used to prompt the player if they want to play again once the game is over.

Making Santa-Tac-Toe part 3 of 4

 Part 3: Random Moves Meet Monty Carlo

Thanks in small part to AlphaGo, there is a huge interest in Monty Carlo Tree Search (MCTS). As the name implies, this is built off the idea of a Monty Carlo Simulation, where you run a large number of random simulations to help determine the best configuration of what is being simulated. Tic-Tac-Toe is too simple for MCTS, but the simulation aspect would be simple to implement and could be interesting so lets do that. We will then look at what would need to be done to turn the simulation into a proper MCTS AI. 

The heart of a simulation is the ability to play a random game. This is simply a matter of making random moves until the game is in a win or tie state, at which point we return the state of the game so we can keep track of the wins and losses.

playMockGame(board, curPlayer) {
    let b = new TTTBoard(board.getTemplate());
    let state = b.getGameState();
    let p = curPlayer;
    while (state.state === TTTConsts.PLAYING) {
        b.setTileByIndex(super.getNextMove(b, p), p);
        p = (p === TTTConsts.X) ? TTTConsts.O : TTTConsts.X;
        state = b.getGameState();
    }
    return state;
}

We want to score each potential move that a player can make, so simply loop over all the moves adding them to our scores array which we will be using for the next move method that our API requires we implement.

buildScoreBoard(board, curPlayer) {
    let scores = [];
    for (let i = 0; i < 9; ++i)
        scores.push(this.scoreTile(board, i, curPlayer));
    return scores;
}

Scoring a tile is simply a matter of making sure the move is valid, followed by playing several mock games and counting how many of the games the AI wins versus the losses.

scoreTile(board, index, curPlayer) {
    if (board.getTileByIndex(index) !== TTTConsts.EMPTY)
        return -2 * this.trials;
    let winState = (curPlayer === TTTConsts.X) ? TTTConsts.X_WON : TTTConsts.O_WON;
    let loseState = (curPlayer === TTTConsts.X) ? TTTConsts.O_WON : TTTConsts.X_WON;
    let score = 0;
    this.testBoard.clone(board);
    this.testBoard.setTileByIndex(index, curPlayer);
    let opponent = (curPlayer === TTTConsts.X) ? TTTConsts.O : TTTConsts.X;
    for (let i = 0; i < this.trials; ++i) {
        let state = this.playMockGame(this.testBoard, opponent);
        if (state.state === winState) score += 1;
        if (state.state === loseState) score -= 1;
    }
    return score;
}

Finally, implementing getNextMove is simply a matter of calling buildScoreBoard and then picking the highest score. We add a random value to each score as a tiebreaker.

getNextMove(board, playerToMove= TTTConsts.EMPTY) {
    let scores = this.buildScoreBoard(board,playerToMove);
    let index = 0;
    let high = scores[0] + Math.random();
    for (let i = 1; i < 9; ++i) {
        let temp = scores[i] + Math.random();
        if (temp > high) {
            index = i;
            high = temp;
        }
    }

    return index;
}

The MCTS algorithm is a bit more involved than what we are doing, but with such a small tree, implementing a full MCTS is purely academic. We would need to track a bit more information for each node in the game to properly do MCTS. Lets quickly take a look at the algorithm. It is broken into 4 basic steps.

1 Selection. The idea here is that we pick a node that we want to explore further. This is usually done by looking at the win/loss ratio in combination with the times the node has been looked at for the nodes that are not fully expanded. We want to pick the most promising node but at the same time want to make sure that each node is explored enough to properly estimate it’s worthiness. There are many methods to do this though the simplest is to use threshold * (wins+1)/(plays+1) but there are better methods available.

2 Expansion is simply to add one of the unexplored nodes of the target onto our tree. Instead of just having a scoreboard for the current round, we would need to track all the nodes we have expanded in some type of tree structure and keep track of the win/loss ratio for all of them.

3 Simulation (playing random game), what we are doing already.

4 backpropagation. Taking the score the expanded node received and passing it through all the parent nodes adjusting their probability. Remember to consider who has won so that you invert the win/loss ratio from opponent nodes.

The big issue here is that it is easy to run out of memory as you expand. One solution to this is to cap the number of nodes allocated and when you run out of nodes go into a pruning stage where you remove nodes of poorly performing choices. A node pool is a good way of doing this as when the pool is empty, you do a pruning pass adding pruned nodes (including children) back into the pool.

Now that we have several AI agents, we can put together our Christmas game. This will be covered in the next part.

Making Santa-Tac-Toe part 2 of 4

 Part 2: Solving Using a Tree

With the basic game class that was created in the last part, we are ready to create a better player to play against. This is where the computer can have an advantage over us humans as they can examine many more moves per second than we can. This allows more exploration of the possible moves, and with a simple game like Tic-Tac-Toe, can even explore all the possible moves when deciding what move they wish to make. How is this possible? When you think about a game, it can be represented as a tree structure as shown in the image below.

The first move has nine options. The second has 8 options for each of the 9 boards. The third move has 7 options for each of the 72 boards and so on. The total number of board configurations is 9!, which is 9 factorial or 9x8x7x6x5x4x3x2x1 for a grand total of 362,880. As each move leads to a set of other moves, the game can be represented as a tree. The AI then just hast to start on the node of the tree representing the current state of the board then find the move most likely to win. There is one problem, namely that the opponent also wants to win.

We need to be able to pick the best move to make for the computer while also assuming that the opponent will always pick the best move that they can. This may sound like a problem, as what happens if the opponent doesn’t pick the best move? The answer is that the AI will still be in a good position, possibly even able to win the game faster by taking advantage of the mistake. Still, if you are using some of the pruning techniques we will be discussing, this could be a problem as the AI may not have stored information about that move and will have to search from scratch.

The basic approach then is to recursively search the tree taking the best move from whoever the current player is.  As the opponent winning is bad for us, we will invert the score from the opponent so will weigh the moves that the opponent wins as an undesirable position for us. This is implemented as a recursive pair of methods.  ScoreTiles simply takes a board and scores each possible move on the board by calling scoreTile. ScoreTile checks to see if a particular tile is a valid move and if so if that move will result in a win. If the move is not an immediate win or tie, we need to look at the next moves in the game taking the highest score from that and inverting it. This recursion will repeat until a winning or tie move is reached.

scoreTiles(board, curPlayer) {
    let scores = [];

    for (let i = 0; i < 9; ++i) {
        if (board.getTileByIndex(i) === TTTConsts.EMPTY) {
            scores.push(this.scoreTile(board, i, curPlayer));
        } else
            scores.push(TTTConsts.INVALID_MOVE);
    }

    return scores;
}

scoreTile(board, index, curPlayer) {
    if (board.getTileByIndex(index) !== TTTConsts.EMPTY) return TTTConsts.INVALID_MOVE;
    this.testBoard.clone(board);
    this.testBoard.setTileByIndex(index, curPlayer);
    let winState = (curPlayer === TTTConsts.X) ? TTTConsts.X_WON : TTTConsts.O_WON;
    let state = this.testBoard.getGameState();
    if (state.state === TTTConsts.PLAYING) {
        // recurse
        let rboard = new TTTBoard();
        rboard.clone(this.testBoard);
        let opponent = (curPlayer === TTTConsts.X) ? TTTConsts.O : TTTConsts.X;
        let scores= this.scoreTiles(rboard, opponent);
        let highIndex = 0;
        for (let i = 1; i < 9; ++i)
        if (scores[highIndex] < scores[i])
            highIndex = i;
        return -scores[highIndex];
    }
    return (state.state === winState) ? 1 : 0;
}

The getNextMove API call then simply calls the ScoreTiles for the existing move and picks the move with the highest score.

getNextMove(board, playerToMove = TTTConsts.EMPTY) {
    let scores = this.scoreTiles(board, playerToMove);
    console.log(scores)
    // return best move
    let highIndex = 0;
    for (let i = 1; i < 9; ++i)
        if (scores[highIndex] < scores[i])
            highIndex = i;
    return highIndex;
}

The search tree for Tic-Tac-Toe is a small enough tree that we can fully explore it, but what if it is not? More complicated games may not allow for us to search the entire tree in a reasonable timespan. For these games we need to come up with a different way of scoring the state of the board. This will be game specific, but one approach I would consider if there is not a good way of finding a weight for the board would be to recurse to the desired end depth and then simply do a series of random games and return a score based on how many wins occurred. Limiting the depth that you search also is a way to reduce the difficulty of the game.

To speed up searching, there are ways of pruning the search tree. If you assume that your opponent will always take the winning move if it is available, you can stop searching for an opponent move once there is a winning move available. This may not sound like much but can reduce the search by a surprising amount. 

One of the new and highly effective ways of picking moves is the use of the Monty Carlo Tree Search algorithm. We will not be implementing the full algorithm but will do the starting point and explain the algorithm in the next part.