Tag: pathfinding

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.

Latest Fixes: Pathing for Pixel-Accurate Movement

Today was focused on getting the monsters to behave as intelligently as they did back when movement was tile-based.

  1. Monsters uncrowd when they are overlapping (should pretty much never happen in general, but sometimes they spawn in the hitbox of another creature). If an intersection is detected between two creatures, they get an override that compels them to move away from each other for a few frames.
  2. Cardinal directional movement replaced with simple vectors, to allow for diagonal movement.
  3. When monsters have a line of sight and can walk directly to a hero, they use 8-way movement to get there. I added a bit of tolerance to the check to prevent the monster from zigzagging when on the same X or Y coordinate.
  4. Without line of sight, the monsters fall back on pathfinding (that is, if the monster is intelligent enough.. more on AI changes in another post). Just like with direct walking (which I call Gauntlet Movement in the code), it uses 8-way movement. This was really easy to do with my existing path mapping: it just checks the 8 adjacent tiles by including directions, rather than only the 4 adjacent tiles in cardinal directions.
  5. When monsters are in melee range, they can attack in 8 directions.

A quick word on diagonal movement. In many games with two-dimensional movement, the X and Y movement vectors simply get combined, and not adjusted for the trigonometry. Bishop movement becomes unnaturally faster than rook movement in this case. Think Doom II or Secret of Mana.

Traditional diagonal movement just combines X and Y to give you this nice diagonal reach.
Traditional diagonal movement just combines X and Y to give you this nice diagonal reach.
The "proper way" to do it adjusts diagonal movement to about 70%.
The “proper way” to do it adjusts diagonal movement to about 70%.

After spending so long with these games, my adjustment to trim diagonal speed actually feels like a real debuff. It seems slower even though it’s the same speed. For now it’s still in there, but I’m not sure what I’ll do later. A friend suggested the fast diagonal movement be a powerup.

We’re Off The Grid (mostly)

Pixel based movement is in.

When monsters form a full horde of 10 or more in one location, they sometimes overlap a bit, so that’ll need to be ironed out. Pathfinding needs to be updated to use 8-way movement, not just 4-way movement. Line of sight works really well. It definitely feels more like Gauntlet this way–once the systems are all working properly, I can test it out in the context of the whole game. Overall I’m excited about where it’s going.

Numbers are node weights. Shortest path to summoner is as easy as picking the lowest number in the squares adjacent to you.
Numbers are node weights. Shortest path to summoner is as easy as picking the lowest number in the squares adjacent to you.