Hoping for some advice on AI pathfinding terminology
Basically I have a town made of individual hex shaped tiles with buildings on them. Each tile will have footpaths too, and my little people will hopefully wander around the paths, travelling to other tiles via their path connections.
I’m fine with learning this stuff but just not sure exactly what terms to search for to get started!
Should I be looking up specific #Godot features for finding routes? Algorithms? Help!
Basic #pathfinding is not hard. What hard is to make it use less resources and calculate as much paths as possible.
I just throw at you some links to study:
* How to implement A*
https://www.redblobgames.com/pathfinding/a-star/introduction.html* How to optimize A* for bigger maps
https://www.youtube.com/watch?v=RMBQn_sg7DA
https://www.youtube.com/watch?v=anGdYJu_eH4
https://web.archive.org/web/20190411040123/http://aigamedev.com/open/article/clearance-based-pathfinding/deleted by creator
@teahands @gamedev you probably want to start by looking up A* pathfinding. Essentially it’s just a way of calculating the shortest route between two places by scoring each adjacent tile from every other, based on how many hops it took to get there. Same maths however many adjacents you have so it should work for hex quite nicely. I’m 99.9% certain a YouTube search will explain better than I can…
Posted this from Mastodon basically just to see if it would work, which it does. But also gives me a very small character limit so if the question makes no sense and you need more info, let me know. Expertise very much appreciated!
Hmm, I have some tips.
Start from the source and destination, and send out 3 rays in three threads, on biased towards the left, on biased towards the middle, one biased towards the right. Have them jump randomly to a tile according the their bias at like a 65/35 ratio, starting from the source and destination. (This gives you 6 threads) And you can keep the map data in memory. Just loading in the cords of each unit you need to calculate with arguments.
When you finish, you clean up the paths, by finding where the paths run adjacent to each other. Then you calculate the total length, and pick the path that’s shortest.
An additional optimization is you take the last two numbers of the ID, or convert the letters to number, and divide this into 60 frames, so you spread the load across 60 frames instead of calculating the path for every object every frame.
You can extend this to move between zones by, making each portal represent a list in locations it can access, with perhaps a score for how long it gets there, but that’s complicated.
You basically just want to make a list of objects you need to pathfind, divide these objects into 60 somehow. Using the ID is a fast way to do it. For each object, calculate the shortest path using any number of algorithms or design one yourself. You have to have an interface between your pathfinding algorithm and your map data. You could generate a map of walkable tiles to make this easier as well. Another cool optimization is you can weight certain tiles by how desirable they are to walk on, so a sidewalk would have a score of 10, and grass a score of 5, and a wet area a score of 1.
This might be way too complicated. You could try to implement a simple algorithm like put your hand on the left wall and follow it and then delete loops where the paths are next to each other. This is how you get out of mazes. You could try just sending two rays directly towards each other and then moving over one if it hits a blockage. The problem with these simple algorithms is they look unnatural or may fail. You should at the minimum implement route optimization by cutting out unnecessary loops, and use multiple routes to see which one is the shortest which will make even simple algorithms appear much more natural.
Most game engines should have some kind of basic implementation. ChatGPT is really good for stuff like this. Little code bytes, helping you debug, and learning theory. Just feed it back the debugger output, and keep things simple and in small bites, so it doesn’t get stuck so much or generate a lot of broken code at once that’s hard to debug.
@teahands @gamedev A* (“A star”) might be a friendly starting point. It’s generally intended for square grids, but a little algebra to get the right distance for the angles might make it possible to extend to hexagons. Even if you don’t end up using any part of it, just understanding it might help for fundamentals.
@bluestarultor @gamedev Fundamentals is absolutely what I’m missing here so thank you very much. Baby steps, and all that!
deleted by creator
