soulcaster – Page 2 – MagicalTimeBean

Pathfinding Exhibition

I’ve gotten things to a state where it’s good enough that I want to show it off. This video shows all the features I’ve put in place, and what happens when they’re removed. It’s kind of like that elementary school science experiment where you bake several batches of cookies and leave out a different ingredient each time, to see the results.

The pathfinding AI is a collection of features:

Gauntlet Movement: Monsters move towards the summoner. They will slide along walls with diagonal movement, but can’t navigate around corners and will get stuck easily.
Sidestepping: Even without any maze solving code, the Gauntlet movement can be improved a bit. When monsters sense that they have been blockaded for about one second, they randomly try moving in a diagonal towards the summoner, which helps them get around walls.
Raw Pathfinding: A maze solving algorithm points the monsters towards the closest viable path to the summoner. If the monster has a direct, visible path to the summoner, it switches back to Gauntlet movement, because that tends to be faster than using the path. Notice how the rats on the right side get stuck because they get to the doorway at precisely the same time. I call this the Three Stooges Effect, and I came up with a pretty cool solution for it:
Traffic Fields: A traffic director data type watches the monster movement, and adds vectors to each floor tile. If a monster tries to walk on a tile that has a vector pointing in the opposite direction, it gets blockaded just like a wall. This way, whoever gets there first sets up the flow of traffic for that particular tile. Each vector times out after a second or so of inactivity, which lets the patiently waiting rats through. Look at the rats on the right now–they are behaving so orderly! Even though both rats reach the doorway at the same time, the top one got evaluated first, got its movement vector placed there, and successfully repelled the lower rat (and all his friends). The visualization lets you see the tile vectors as arrows.
Creature Weight: The numbers you see on each tile in the Traffic Field visualization are the “weights” of each tile. These are used in the maze solving algorithm. They actually represent the number of steps it takes to get to that particular tile from the point of origin: in this case, the summoner. The fastest route is easily generated by starting at the monster’s location, and just picking the lowest number from the eight available directions. With creature weight taken into account, any tile occupied by a creature gets its weight bumped up by a couple points, or 5 points if the creature is blockaded. Notice how the rats don’t all take the same path: once a few have started using a particular route, the weight to cross it is now larger than another route. Not only does this decrease the time it takes for a large crowd to solve the maze, but it also has the great side effect of flanking.
Uncrowding: This last one is subtle, but makes a difference. When a monster has been blocked for more than a couple full seconds, it picks a random direction to move which is roughly in the opposite direction they were originally trying to go. This breaks up congestion and slightly improves the maze solving time.

At this point, the pathfinding AI is good enough to leave alone for a while. I just wanted to get it to a point where the monsters don’t get stuck, and you won’t be able to cheese them (at least not easily).

Collision Purgatory

Pixel accurate movement has taken a bit longer than I thought it would. I was expecting about one week to get things operational–I think I got 75% of the way there in a week, but now it’s the final 20% that could take up 80% of the time.

Pathfinding and general movement works, but needs hacks to work properly. I created a system to help the monsters file through doorways without getting stuck, but it still relies on a system that temporarily disables clipping for monsters that get stuck together for too long. That system works great for declogging the doorways, but when the monsters get close to the player and start phasing through one another, they just stack in a jumbled, writhing mess. I really want it to look like Gauntlet, with mobs flowing gracefully around corners and stacking into nice grids.

I think my collision detection will also have to move from floating point to fixed point, because accumulation errors are probably one of the causes of clipping bugs among monsters. That change will take at least two days, if not more.

I’m pretty confident it will have been worth the trouble once everything is together. For now, it’s in that purgatorial state where the code is broken and ugly… not a place I like to leave things.

Pathfinding Test With 30 Rats

Pathfinding is operational. The rats intelligently pick new routes to flank the player and avoid congestion in the long term. What they don’t do very well yet is avoid clogging up the doorways when they’re already bunched up. They also unnecessarily zigzag a bit, slowing them down and making them look just a bit more insane.

I have an idea I’m going to try tomorrow that might fix the clogging around doorways. The monsters will have access to a traffic map that tags each tile with a movement vector. They all start out neutral, and when a monster moves into a tile, that tile’s vector is set to match the same direction as the monster’s movement. When inside a tile, a monster has to move along with the current, or vacate the tile. Currents get reset with a timer, so if a monster hasn’t walked on the tile for a few frames, it gets neutralized.

It’s an unusual system, so I don’t know if it’ll work yet, but it’s worth trying.

To fix the zigzagging, I can set the monsters to keep a course for longer. Once they are in sight range of a hero, though, the zigzagging will stop because they stop pathing altogether at that point.

Level Analysis: Soulcaster 1

A procedural level builder needs to be able to make fun levels.

It took me a while to get the hang of what is fun to do in the Soulcaster world–when making the first Soulcaster, I probably made about 30 bad levels before I found my footing and made some good ones. In this article I will take a closer look at some of these (the good ones), to see how they are constructed, what experience they offer, and how they might be broken down to be generated procedurally.

One advantage to the pattern-based room generator currently in SC3 is that, worst case, I can just build a large collection of intact levels with some basic parameters, then stitch them together randomly to build the game world. This at least offers the craftsmanship of prefab levels, but kept fresh for each replay. I’m not setting out to make an algorithm that could generate these levels from scratch–that would take way too long. Instead, I’m looking for ways these levels could be broken down into basic elements that could be swapped out, flipped, rotated, inverted, and otherwise manipulated.

Some levels will be only slightly dynamic, while others will have lots of parameters and will be vastly different every time. I think we’ll need a good balance of both of these types to make a solid experience.

Let’s start with the simplest level, the Cellar.

This is a great example of a room that’s best left intact. It has a few waves of enemies that appear from the barrels, controlled by a combination of floor switches and natural progression by killing foes. Maybe later down the line I could find a way to add dynamic parameters, but that can be put off until alpha or later.