4 Hugues Ross - Blog: Capstone Update 2: The 1st Concept
Hugues Ross


Capstone Update 2: The 1st Concept

Now that capstone is underway, our group needs to begin prototyping some of the many ideas that we've been throwing around. The first idea that we've decided to use plays off of a common trope in many games. Have you ever wondered, in a dungeon, why none of the traps are sprung? Have you considered where all of the gold and treasure chests dotting these caves actually comes from?

Enter the restocker.

The point of this game is to enter dungeons and restock them, by resetting traps, refilling chests, and strategically placing corpses with loot. At the end, your performance is graded based on various criteria, like the time it took you and the distribution of the treasure.

Mechanics: Scoring

I'm not going to talk too much about the gameplay itself, since the first prototype isn't even done yet. However, I want to address one question that I was asked while we were discussing the game. The issue that came up was how we could actually grade the player's treasure placement, and I came up with an interesting solution for us to try. Using a technique sometimes referred to as Dijkstra mapping, we can generate heatmaps of important elements in a level. From that, we can analyze how well the player placed treasure, and we can tell whether it's too spread out, to clumped up, or even. We can also theoretically make our own heatmaps of how we think treasure should be distributed, and compare them to the player's results.

Dijkstra Maps

I'm going to go out on a limb here, and assume that you likely don't know what a Dijkstra map is. If you have any experience with game AI, you probably know about Dijkstra's algorithm. Variants of this algorithm, such as A*, are used for pathfinding. Essentially, it works by starting at one point and expanding outwards until the destination is reached or the map is filled up.

With Dijkstra mapping, we perform a version of this from multiple starting points and with no destination. In addition, we can give each starting point a value and make it count down as it radiates outward. If we keep the highest values, then the result is a heatmap generated from the points used. From here, there are a variety of things we can do with the resulting data. One option is to check if lowest value is above a certain threshold, which ensures that no part of a map is too far from a point. Here are a few examples:
1 emitter, no walls
1 emitter, walls
3 emitters, walls

If you compare examples 2 and 3, you'll notice that the values are much higher (redder) as a whole in the latter. This is the general goal here. By spreading out multiple emitters (chests), the resulting values will be much higher than if we place just one in an area or bunch them up.

No comments: