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!
@teahands @gamedev I think the term you are looking for is ‘A-star’.
Godot has build-in A-star algorithm for use which is best for tile-based (or just a lot of pre-defined points like in 2000s FPS) pathfinding, somewhere in scripts.
And it has more fancy navigation which is more for free-flow polygonal world. That is something far more complex than A-star, like ‘just use library we have’
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/@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!
deleted by creator
@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!
