[Request] Node Pathfinding Plugin

Recently I've been trying to come up with a good method of pathfinding in a platformer game. A node-based system seems like the best way and I have some ideas on how the nodes would work, but for the actual searching of which nodes need to be reached to get to the goal (A* and the nodes doing their work), I think a plugin would be far better than events. C++ is much faster for this than writing it all in events. What I'm doing wouldn't require very many nodes though, so if it could be done in events fast enough and someone has any advice on how to set up A* and nodes, I'd appreciate that, too.

And I inadvertently suggested this sort of plugin in the Platforming AI topic, haha.

Anyway. The RTS movement is based on A*, stick an obstacle with the 'solid' attribute in the middle of the "RTS Basics" template and the units will automatically move around it, as well as any other RTS units. However, I think this might be difficult to utilise for a platformer, since it's an RTS Behaviour, so, someone could well possibly use the code on the SVN as a base for a platformer pathfinding behaviour.

Make it compatible with the Custom Movement as well, plz.

Edit: Ah, what the heck. I might as well set up a 'design' for how such a plugin could work and what it could do.

Needed Functions

• Identifying solids and platforms that the AI can land on, and working out routes to take to a destination based on the environment using nodes. The AI should also be able to drop through platforms, if it can't do this, it will find another route.
• Using objects, families and attributes to identify objects that the AI should actively avoid, which creates nodes with each tick. Of course, the event should also be able to set the 'margin for error' to allow the AI to 'make mistakes', since it would be no fun if the AI, say, could perfectly avoided every attack you throw at them.
• Being able to set a 'target' to chase after, and how much distance to stay from said target (for example, you could set the current position of the mouse as the target ). Or set a destination via events.
• In general, being able to set the 'behaviour' of the AI in how it gets to a destination. The AI can try and get to its destination as fast as possible either while being as careful as possible or being downright suicidal about it, or the AI can take it slowly and more carefully. Or just as suicidally. Your choice.
• The AI could be given a certain 'task' if there is no active destination or target. For example, the AI can wander within a certain range, or just wander aimlessly.

With Platform Behaviour

• If the same object has the Platformer Behaviour, the AI will use the behaviour's variables, eg, speed, jumping strength, etc.
• Not much else here, really, the AI uses the behaviour to move around.

With Custom Movement Behaviour

• Since, obviously, the Custom Movement's stuff is done in events, if the object has the behaviour, the AI will take values defined by events (variables are recommended) in place of the variables used by the Platformer Behaviour.
• The controls, such as moving around, jump, etc. Are also handed by events. In order for this to work, the Function plugin is required. The developer just needs to identify to the AI what the controls are, and what Functions are tied to them, and if a function is not being called while the AI is holding a 'virtual key' down, the AI will stop hold the 'virtual key', and try pressing it again.

Optional Functions

• The AI can be 'made aware' of additional abilities that it can perform in order to gain greater speed or horizontal/vertical distance, using functions and controls. These additional abilities would need: ** Maximum Distance/Speed gained ** A 'Priority' value, as to how often the ability should be used in certain situations.
• The AI can use certain functions/controls to identify attacks that it can perform, similar to additional abilities, but in a certain distance from an identified target, and if certain conditions are met. Such events would require: ** Minimum recommended distance from the target (the AI will either ignore or note this value depending on its behaviour) ** Maximum distance from the target ** A 'Priority' value, as to how often the attack should be used over other attacks.

Well, that's all I've got for now, but I might update this later.

Those are some great ideas, Candescence! It's actually a lot more features than I was thinking of. I was thinking of a plugin that only handles the A* search and you get numbers from (which nodes are next in order) and I was going to implement the AI part myself. Of course, if it could work as well as the Infinite Mario AI, I wouldn't need to do that ... Also, Infinite Mario AI doesn't even use nodes (which is seriously impressive,though I wonder how something like that would work in non-linear levels).

For nodes, I think it would be great to have a way to visually connect them in the editor. As in, you could draw a line between them (like with the line object or a sprite) and the program uses that to gather all the connections data.

In layman's terms can you tell me how A* works given platform physics?

Actually, I think I have an idea...

* Use a larger set of nodes to automatically generate the 'routes' that the AI can take, taking into account platforms and level layout.

* Use the Infinite Mario AI technique of "close nodes" for short-term decisions, like avoiding projectiles or enemies. Thankfully, the Mario AI code is open-source, so anyone can check it out and figure out how it works.

newt: One of the images here gives a rather useful idea of how A* works, well, for Mario, anyway. Basically, A* uses points, or 'nodes' to determine where an AI object should go in each tick, in order to get to a goal in the shortest possible distance. If there is an obstacle where certain nodes are, the AI will ignore them and consider other nodes instead.

Using the third image in the link I provided, the first slide shows a rather basic bunch of nodes (there are generally a lot more of them), representing certain actions Mario can take, like jump to the left, go to the right while speeding up, and so on. It will pick the best option first (in this case, going to the right fast, since the goal is the end of the level), but when this is evaluated, in the third slide, there is an enemy on that node, so the AI 'backtracks', declares that node a no-go, and then picks the next-best node - jumping over the enemy while also speeding up. The AI will then pick the next best node after that, and so on.

Even if someone will create a platformer pathfinding plugin, I'd still like to have a plugin specifically for doing A*. It would be useful. I'm not sure how it would gather the data on nodes and their connections, but I know someone can come up with something.