EverEnding DevBlog 129: Pathways

EveHeader

Progress has been going slow, but it’s progressing. I’ve been slowly building up the behavior code for this enemy type, but I realized a couple of days ago that I’m probably going to need a robust pathfinding solution rather than something kind of half-assed, so the last few days have mostly been research into how pathfinding works, specifically within the context of a 2d platformer.

I’ve got a pretty good idea of the kind of approach I want to use now. This is taking a long time and it’s been a week or two since I’ve made visible progress in the game. which is frustrating: But, the good news is that whatever I come up with here should be highly generalized and reusable for pretty much any 2d platformer I make in the future.

Here’s the algorithm I’m currently planning on using, (copied largely from the daily devblog, where I came up with this approach yesterday):

Step 1: When each level is loaded, generate a navmesh. This is basically just a fancy name for a grid with every ground tile marked, a ground tile being defined as any tile with a slope of 1 or less that doesn’t have a solid tile of some sort directly above it.

Step 2: Run the A* algorithm as described in this video with the start value of the ground tile beneath the entity and the goal of the ground tile beneath the player. Non-ground nodes are disregarded for parenting purposes, so ground surfaces are parented to whatever the last ground surface was navigated from to reach them rather than the closest non-ground tile.

Step 3: When a path is completed to the player, perform the following tests to make sure that it’s valid:

  1. Above each ground tile, ensure that there’s enough clearance above to allow the entity through. I realized today that I can speed this up by storing the available clearance above each tile in the navmesh generation phase.
  2. At each gap between ground tiles, ensure that the entity’s jump is powerful enough to reach the other side of the gap
  3. Ensure that, if jumping, the minimum-possible jump will not be obstructed. It doesn’t matter if the maximum jump is obstructed: If the minimum is obstructed and the obstacle is possible to jump over, it should have its own ground surface nodes that can be navigated by jumping and get caught in subsequent passes. This assumes that all ground surfaces are navigable.

Step 4: If any of those tests are failed, revert the path to its earliest failure point, mark that node connection as intraversible, and try an alternate path.

It’s entirely likely that I’ve overlooked something with this algorithm, but it’s a good solid plan to get started with.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: