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.