- Home /
Path Finding using 2 dimensional array
Hello,
I am making an RPG. The entire game is based on a 2 dimensional array. The array consist of an object (or class) that holds reference to the occupant. This is how I am evaluating whether or not each node, if you will, is empty. I am using this method to handle the movement, and combat. However, I need help with an algorithym that gets the current position or index of the enemy in the array, and finds the correct path to the player's index. For example, if the player's index is [5,8] and the enemies index is [3,7], then the enemy has to travel to the right two times and up once to reach the player.
Any help would be greatly appreciated, thanks!
If it's a small array, you could first find all branching points (ex points that you can move in 3 or more directions. Then take those points use code to "trace" the possible paths. Once the shortest path is found, then move the enemy.
@n314p This algorithm is quite slow however even on small grids, and would be quite impractical on anything game-sized, especially for multiple enemies.
Also, an unrelated optimization note- If there are very few types of classes, and they each do specific things, don't make it an array of classes. Ins$$anonymous$$d, keep a lookup table with one of each class in it, and make the array itself an array of structs, with an int that points to the type of class in it, and possibly some other commonly used data. Say, if most occupants have a health, then a float for a health value.
This means your CPU doesn't have to go chase down references to everything, and can just pack a lot of data into its cache, which is a lot faster and saves a decent amount of memory as well.
I'm actually not familiar with structs. I am currently reading into them and finding they are nearly identical but less expensive. I'm not too far into my project, so I'll def give it a shot.
Be careful with their apparent similarities...
The main difference is that a class is stored in some random place in memory and a variable of that type is just a pointer to that memory, whereas a struct is actually the data itself, right there where your variable is.
$$anonymous$$ost of the time, you use classes, because its often faster and easier to pass a reference around, and you don't have to copy any memory. You can easily have 2 variables referring to the same data, for instance, and you don't much have to care about how often you pass a class around since it's only just passing around a pointer and not all of the data it points to. But....
Computers don't like doing things randomly, and finding the data that a class pointer points to takes time (About 100 ns to be specific). Which is why you don't want to be doing this over large datasets. 10 random memory reads is a microsecond, and you only have 1600 of those every frame to get 60fps. Luckily, your cpu has a cache, which is basically a piece of small, fast memory. The site linked earlier gives a number of about 4 nanoseconds for the L2 cache that your data will probably be in. This is a lot faster, but it can only load data that is consecutive in memory.
And thus, structs. Since they're not pointers but the data themselves, an array of structs has all of the data stored side-by-side. Your CPU will load entire blocks of that data into the cache at once, and you can access them really fast. Additionally, they're easier on your GC since they don't need to get moved around much.
BUT WARNING:
Don't replace all of your classes with structs! They are different tools for different things. For one, structs can't inherit, so you lose polymorphism. Second, assigning a struct to a different variable makes a COPY of it, not a REFERENCE to it. Generally it's better to use classes for anything you would consider an object in code, and structs for anything you would consider a value. Int and float are values, and it makes sense then that Vector3 is also a value. But $$anonymous$$onoBehaviour is an object, and would make no sense as a struct.
Look up CPU caching, there's a lot of really neat optimizations you can do to make your code orders of magnitude faster in some cases. It's part of the reason why Unity ECS is so fast, for instance, even without the burst compiler. Sequential data is almost always better than random access.
Answer by Zarenityx · Aug 14, 2018 at 07:56 PM
Check out A* Pathfinding. It's really simple to set up (Here's a good tutorial). At the most basic level, it works like this:
Your enemy moves in a sequence of 'steps', where it moves to an an adjacent tile. Each tile you can 'step into' has a cost, and your enemy picks the one with the lowest cost to move into.
Each tile's cost is the sum of 2 things:
-The cost to move into that tile (the tile cost)
-The estimated cost (called the heuristic) between that tile and the destination
Looking at the 8 tiles around you (4 if no diagonal movement), calculate the total cost for each, and move there.
The Tile Cost:
This is the simplest part of the cost, and the one that you will likely modify the most in your game. Obstacles will have a cost of infinity. Alternatively, you can simply check if it's an obstacle and not evaluate cost, since you know you cannot move there. Other tiles will generally have a cost that is inherent to the tile. Walking on road tiles might cost less than walking on grass tiles, so your pathfinder will prefer to take the roads unless the grass is a big shortcut.
A very common part of the tile cost is simply distance. Moving horizontally or vertically is only 1 tile away, but diagonal moves might work better with a distance cost of 1.41 (sqrt 2). This will accurately weigh each tile with its distance, so your pathfinder won't zigzag as much. Keep in mind that this is only to account for diagonal moves. Your pathfinder should only ever move 1 tile each step, and this cost does not account for tiles farther away than this.
The Heuristic:
This is the real meat of the algorithm, but in most cases its still very simple. The Heuristic represents the cost of moving from that tile to the goal. Ideally, calculating this doesn't require any extra searching, and can be done just with the position of the tile and the position of the goal. This is just Euclidean distance, the square root of the sum of the squares. If your pathfinder can only move horizontally and vertically, you can use the (even faster) Manhattan distance, which is just the sum of the absolute values of the differences in X and Y. Other heuristics exist, but are a bit slower to calculate. These include summing the costs along the line to the goal, etc. You might be able to get away with these if you do it in a background thread in a turn-based game. Generally its not worth it, and if you want the most realistic pathfinding out there, there are better algorithms. A* is great for games though, and it's very predictable.
Tiebreakers and backtracking:
Sometimes, two tiles might seem equally good choices. In this case, there's not much to do other than to just pick one. This can be done either just as an inherent part of your loop (do you replace on < or
Putting it all together:
Consider your enemy having a speed that represents how many steps it can take in a given time (turn, second, whichever. I'm going to be using a turn-based example, it's pretty similar for realtime). Each turn, your enemy finds the cost of all the tiles it can move into, then chooses the best one and moves there. Then, if it still has steps to do, it does it again. And again. This continues until the enemy has either reached its goal (the player), or the maximum number of steps it can take that turn (its speed).
The A* algorithm isn't the most accurate in existence, but its really fast and it works quite well for stuff like this. It's also a lot of fun to mess with the costs to create interesting effects. A ranged enemy, for instance, might actually cost more to get too close to the player (of course this results in the enemy 'orbiting', so you might want to avoid that too, unless you want it).
Underrated Comment. ^ I just screenshot' this for later :)