3
\$\begingroup\$

I'm looking into implementing AI in my 2D side-scrolling platformer, and I'm looking into using algorithms such as A*. For many kinds of pathfinding, we need some sort of grid or systems of nodes or polygon areas. My problem is that I am using Box2d for physics and I am not sure how best to create a structure that my AI can use besides placing individual nodes manually (something I really want to avoid) and using some sort of steering behavior.

My level design is tile-based with each tile being about half of the height/width of my main character. The tiles are not all square (some are sloped). I'd like to have a system that can see what the terrain looks like for pathfinding and also keep track of the positions of other actors such as enemies. I'd like to avoid directly placing any nodes into my level design except for possible endpoints or goals.

This question is related: How do you do AI path following within a 2d physics engine like farseer/box2d?, but it doesn't specify what kind of structure I could use instead of a list of nodes. I'm looking for some kind of grid or type of BSP that I can query for algorithms like A*.

EDIT: I am looking for a data structure that meets the following requirements:

  • Can be searched by algorithms like A*
  • Can keep track of objects that move around
  • Can keep track of objects of different shapes and sizes
  • Does not require me to manually create paths or place nodes

When I first load my level, I have a 2D array (actually just a width, height, and string of ints), but this doesn't allow me to track objects that move not to mention other shortcomings.

Improve this question
\$\endgroup\$
3
  • 1
    \$\begingroup\$ If your game is tile based, don't you already have a grid? \$\endgroup\$
    – Ray Dey
    Sep 10, 2012 at 3:23
  • \$\begingroup\$ No, the only grid is in my level editor. All my entities just have a position inside of a Box2D world. \$\endgroup\$
    – Amplify91
    Sep 10, 2012 at 3:57
  • 1
    \$\begingroup\$ @Amplify91 That is still a grid. You can use your level grid and apply A* on it. Your level dictates walkable/nonwalkable tiles. \$\endgroup\$
    – Sidar
    Sep 10, 2012 at 9:57

1 Answer 1

Reset to default
3
\$\begingroup\$

Do you really need path-finding? Most enemy behavior for a 2D platformer can be implemented with some simple rules and sensors. Eg. Have a sensor in front of the entity that detects a hole or a wall and change direction or jump when something like this happens.

You'll need path-finding if your enemy needs to find the fastest route to different targets (eg. a power-up that he wants to snatch away from the player, or the player himself). If you just need a static path from A to B, you could draw that in the level-editor or do path-finding offline (eg. load the level data, perform path-finding on level grid, write the path-data to another file or into the level-file).

Since your level is tile-based, you already have a grid... for every (walkable) tile you place, you can add a node to your data-structure. Ideally this happens when you parse/load the level data. If your entities are able to jump, things get slightly more complicated, but a naive solution would be to add all "air" tiles (reachable with a jump) above walkable tiles to the path finding-structure so that these can also be searched.

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ Yes, I really do need pathfinding. I have (as you suggested) characters that need to follow the main character. Also, the level design has multiple passages (similar to 2D sonic games). I have a 2D array of tiles when I first load the level, but this is not sufficient as I also have moving obstacles. You said, "for every (walkable) tile you place, you can add a node to your data-structure". My question is: What kind of data structure should I use? \$\endgroup\$
    – Amplify91
    Sep 10, 2012 at 13:16
  • 1
    \$\begingroup\$ @Amplify91 You should use a graph data-structure for A*. But A* isn't very well suited for dynamic worlds, because then you have to rebuild the whole graph whenever your world changes. Most likely steering behaviors will perform better. It's hard to tell without knowing how such a level will look like. \$\endgroup\$
    – bummzack
    Sep 10, 2012 at 15:44
  • \$\begingroup\$ I am looking into steering behaviors after all. Thank you for the guidance. \$\endgroup\$
    – Amplify91
    Oct 10, 2012 at 19:10

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .