The pathfinding algorithms seems to work well on a horizontal 2D plane when the enemy can just go around the obstacle. But in my case my enemy character must jump on top of a plateau then turn around and jump on to that floating platform. That’s just a really simple case BTW, more complex ones would involve navigating a space filling curve.
I’m not expert in AI, so take the following suggestion with a pinch of salt. That said:
If your level is static (or has relatively limited moving elements), you might be able to pre-process a “map” – a connected graph – of various movements that the AIs might make – the edges of platforms, other points to which they might jump from a given edge, etc. With some additional work you might be able to have AIs not only path through these maps but path to interpolated points within the nodes of the map: pathing to a point between two edges, or making a jump that does partway to a given jump destination, for example.
[edit]
I just watched that Mario video (which is quite cool, by the way – thank you for sharing it), I believe, and what that AI seems to be doing is producing an immediate plan based on the tiles around it and calculated jump arcs, likely scoring each plan in order to pick amongst them. That might work for you, although I don’t know what the performance is likely to be like, especially if you want your AI to make halfway lengthy plans – the Mario AI seems to be planning only a two or three steps ahead. Additionally, they may have been helped by their levels presumably being tile-based andfairly simple in design.
Do you have a link to an algorithm, by any chance? I don’t seem to be finding one in the quick searches that I’ve done.
Having looked at the videos that you posted, I still think that the algorithm that I outlined above should work. The first of those most recent two videos looks as though it might be attempting various directions, building a path using what is likely a modification of a standard pathfinding algorithm.
However, I honestly don’t see much that’s likely to be very Panda-specific. You seem to imply that you have an algorithm in mind; are there any particular problems that you’re hitting in attempting to implement that algorithm?
Set up your “start” scenario, for example using the bullet physics module, and run the simulation for however long you want. There is nothing that inherently ties simulating physics to rendering the results of that simulation. You just tell the physics system that you want to simulate a timestep of x amount of time, and repeat until the desired total amount of time has been simulated.
Then you would repeat the whole process with the same “start” setup, but different inputs. When you are done you can take the results of those simulations and do whatever you like with it, for example drawing out paths on the screen or analyzing them to select the “best” move.
Is that also possible with Panda’s built in physics?
So far I’m leaning towards marking certain waypoints as jump. But how is one suppose to mark waypoints as a “special” waypoint in the first place. The manual does not say.
I’ve only used panda’s built in physics system a little bit, but it looks like the PhysicsManager class has a doPhysics function that takes a timestep argument. So you could just keep calling that function to simulate physics without rendering.
As far as waypoints, how are you creating these “waypoints”? Are you using Panda’s built in AI? If so I have not used that at all and can’t offer any advice on it.
At a quick glance, that looks like pretty much what I described.
However, as others have asked, I believe: what are these “waypoints” that you’re using? Are they something that you defined, or an element of PandaAI?
As to determining jumps, I think that I’d be inclined to specify that a given waypoint (or connection, perhaps more likely) is intended to indicate a “jump”, along with whatever parameters your jump code might want (a thrust vector, perhaps). (This presumes that I’m using my own waypoint class, which gives me control of what it contains and how its accessed.)
Hmm… How would you mark a vertex in Blender to be a “jump” waypoint? Indeed, you presumably don’t want all movements from any such waypoint to be a jump – the same point might be used for both moving along a platform or jumping in the other direction from its edge, after all.
I suppose that you could leave out the connections between “jump” waypoints; edges would then all specify “walk” connections, and you could do a little extra processing in your game on loading the mesh to identify potential “jumping points”. How you handle that in your game might depend on how you’re making use of your waypoints in general: how are you planning on using the mesh to direct your AIs?
I’m thinking of holding off on the AI since my project is running on a tight schedule.
However, I encourage the community to find a solution to this platformer problem since it seems to be one that has been surprisingly unsolved in a game using this engine.
I don’t understand why you think this problem needs to be solved “in Panda3d”. No part of the problem given is engine-specific. Pathfinding is a completely different topic to the areas Panda3d covers (3d rendering and some physics). Any solution you would come up with could be taken out of Panda3d and written in a new engine and would work just as well.
You would have better luck asking a more general forum like gamedev or something if you’re having trouble figuring out what you need to do. Most pathfinding algorithms rely on constructing a completely separate model of the world to the one the renderer sees. This model is simpler and built to be comprehensible to pathfinding algorithms like Astar. Because of this, it falls upon you to write a method to make the pathfinding model out of the 3d model (or the data that made the 3d model procedurally). There’s no automatic way to do this, and how it’s done depends entirely on the data you have available (which you have not told us about).
As an aside, I feel you’re trying to bite off more than you can chew. There are ways to pathfind in an arbitrary environment but they are much harder to do than a simple rigid grid-based system. The way you talk about the problem and phrase your questions leads me to believe you need to spend more time on pathfinding theory and implementing a simpler method before you try something like this. If you had a grid-based system, you could simply move a character to each node in turn, perform each type of jump available, and record which node it landed on (and how long it took). Then you can write these results out to a file and read them back in at runtime. You can attach some sort of tag to this path to tell the agent that it needs to jump left here to make it to the node it wants to be at.
As a completely different aside, I don’t think “space filling curve” means what you think it means. Otherwise, I’d like to see how you’re using them in a platformer because that could be very interesting.
I think I can address this without violating my NDA…
If you are familiar with the game GTA San Andreas, there was an issue with some of the AI using nodes proper, so recordings were made for some AI’s to follow and perform certain actions. Planes and trains do not use the node files. Trains use paths in the tracks#.dat and there are also paths for several missions and cars. These paths are saved in carrec.img file short for car recordings.
I am suggesting you record the actions for your AI in a data file to follow in areas that nodes will often fail. I would also make a program that records the waypoints and/or commands with a time index. For example;
x,y,z – character location
doing – idle, run forward, swim, jump, dance, etc.
tx,ty,tz – target location (next waypoint)
tindex – time or delay to waypoint
loop – binary switch
The index would let your program know to make adjustments if your AI is going to fast or too slow. I hope you get creative and make a great game. Best wishes.
If your tiles are all equally spread, e.g. you could put a grid over the screen and all tiles would fit, then a grid graph might be the best thing you can do. A grid graph is basically a point graph, but you can generate it procedurally based on your tiles. Your AI agents would need to know how far they can jump in each direction (side, up, diagonal, fall down), which you’d need to consider when calculating them a path.
In case your tiles are not fitting into a grid, you might try using a finer grained grid graph.
