Help with pathing.

[Meiscool]

Ugh, so long story short, I've been coding for around 4 hours now and keep failing at what I want to do.

Basically, I've made a script where the enemy moves towards the hero with a small amount of variability (to make things slightly more unpredictable). However, if there is say... a rock between the hero and the enemy, the enemy will not move around it. So, I wanted to make a pathing script for those times when the enemy has been in the same place for .X seconds. However, every attempt I've done at this has failed.

Does anyone know how to effectively path in rpgm using screen x and y cords and the command terrain ID? I'm using pictures, not events if that helps at all, and I'm using terrain ID to show what tiles can and cannot be moved on. For example, tiles with an ID of 1 can be moved on, but an ID of 4 cannot be moved on by anything but projectiles, and then 9 can't be moved on by anything, etc. Why do I tell you this? So that you'll know that my movement system is still 16x16 pixel grid based.

[Prpl_Mage]

This is one of the things that I got stuck on trying to make a Fire emblem type gameplay. The AI wouldn't recognize obstacles and in the end I had two versions. 1, the enemy ignored obstacles and moved over them. 2, the enemy walked into it and then kept moving forwards without getting anywhere which ended the turn.

So I'm sorry, can't help you out with this. But interested in hearing how it could be solved.

[DragonBlaze]

Dijkstra's algorithm.

Almost all path finding applications from GPS systems to video games use a version of this algorithm. It's pretty fast and works very well, the issue would be trying to get it to work with rm2k3 scripting.

The basic idea is pretty simple. You have a bunch of random locations called nodes scattered across the map. Usually in tile based games, every tile is a node, where as a game like fable or skyrim actually use thousands (probably millions) of nodes randomly placed across the map. These nodes know how to get to their nearest neighbors as well as the cost of moving to each one of their neighbors. The cost is just an arbitrary number that can represent distance, difficulty to cross the terrain, fuel cost, or whatever combination you would like to use. In a tile based system, knowing how to get to neighboring nodes is simple, move up, down, left, or right. If terrain is un-passable don't connect the nodes, otherwise he cost between the neighboring nodes would then be the terrain ID. Then given a starting node (the enemy location) you can find the shortest path to a ending node (hero's location) by examining the cost of each node, and storing the list of nodes with the lowest total cost that gets you from the starting spot to the destination. When your hero moves, you'll have to rerun the algorithm so the enemy gets the new path to take to the hero's new position.

Once you have this 'graph' of nodes set up, you need to design AI to traverse it. Here is the algorithm to do so (though your distances will probably all be 1):

1.) Assign to every node a tentative distance value: set it to zero for our initial node and to infinity for all other nodes.
2.) Mark all nodes unvisited. Set the initial node as current. Create a set of the unvisited nodes called the unvisited set consisting of all the nodes except the initial node.
3.) For the current node, consider all of its unvisited neighbors and calculate their tentative distances. For example, if the current node A is marked with a distance of 6, and the edge connecting it with a neighbor B has cost 2, then the distance to B (through A) will be 6+2=8. If this distance is less than the previously recorded tentative distance of B, then overwrite that distance. Even though a neighbor has been examined, it is not marked as "visited" at this time, and it remains in the unvisited set.
4.) When we are done considering all of the neighbors of the current node, mark the current node as visited and remove it from the unvisited set. A visited node will never be checked again.
5.) If the destination node has been marked visited (when planning a route between two specific nodes) or if the smallest tentative distance among the nodes in the unvisited set is infinity (when planning a complete traversal), then stop. The algorithm has finished.
6.) Select the unvisited node that is marked with the smallest tentative distance, and set it as the new "current node" then go back to step 3.

Unfortunately it's been too long since I used rpg maker to know how to implement this algorithm with events, but if you manage to implement a version of Dijkstra's algorithm, it will guarantee that you will always find the shortest path (you can add variability by adjusting the cost), and it will most likely be the fastest solution as it is pretty much the fastest path-finding algoritm known to man.

[Meiscool]

Thanks DB. You're right that this will be hard to put into rpgm... I know of people who did it with tiled events, but with picture events this might be a very different cup of tea. I'll see what can be done.

In the mean time, I was able to make a makeshift script for moving around objects. It is far from perfect, but it works for the moment, so additional posts shouldn't be needed until I attempt DB's method. Thanks everyone that read this.