Simple pathfinding with Tiled maps

[MisterImpossible]

I'm pretty new with Love2D and I'm writing a simple RPG type game with enemies which will use a basic FSM to control their behaviours, such as patrolling, chasing, attacking etc. I need to implement some form of pathfinding or obstacle avoidance for the enemies for when they are coming after the player and I've tried following some tutorials, but not really understood them very well. Also, it seems like most pathfinding libraries inly account for 2D array based maps, whereas Tiled exports one dimensional maps with collision boxed with the form x,y,width,height.

I was thinking of using Box2D ray-casting for collision avoidance but I'm not sure if that would be a good solution and, ultimately, I'll probably need to use pathfinding at some point anyway.

Sorry if this is a bit of a ramble, but if anyone can help me figure out how to add pathfinding I'd be super grateful. It doesn't necessarily need to be A* as my maps aren't very large or complex.

Thanks in advance.

[RNavega]

Hi. It's quite a big topic, needs some reasonable amount of research until things click.
An important part is that A*, a graph search algorithm, doesn't restrict the shape of the node graph that you're using. That is, when you're starting from a tile map (AKA 2D array based map), it's usual to treat the center of each tile as the nodes of the graph used with A*, with each node connected to the nodes around it. But you don't necessarily have to build the graph like that, even if you're using tiles. You can manually or procedurally place the nodes on the map and just cover the most important points:

ccs-218235-0-87307800-1395091016.jpg (94.75 KiB) Viewed 507 times

Some relevant links:

• https://www.redblobgames.com/pathfindin ... ction.html

• https://tchayen.com/open-problems-of-a- ... athfinding

• https://gamedev.net/tutorials/programmi ... -ai-r4942/

• https://arrow.tudublin.ie/cgi/viewconte ... ntext=itbj (PDF)

• https://ahamnett.blogspot.com/2012/10/f ... rithm.html

• https://www.red3d.com/cwr/steer/gdc99/

[BrotSagtMist]

This this work for you?

main.lua.zip

(3.54 KiB) Downloaded 21 times

Tried myself on tutorial writing sometime but no idea if i make sense.

[darkfrei]

Just create the grid for your map:
1) creating the grid
2) set false to not movable tiles; set zero to the start tile
3) set weights for the orthogonal / diagonal movement as 12 and 17 (almost 1:1.416). (I am adding extra 1 weight for every direction changing; the way will be more straight!)
4) fill the grid from start to finish, adding the weights and write the summ to the next one
5) if the weight was larger, then overwrite it
6) do the logic for the diagonal movement: squeeze not not through the not filled corners
7) if the end is achieved, find the lowest value in the near cells
8) do the 7) until the start, write tiles to the result list. It's the shortest way.

See the example: viewtopic.php?t=93761

[dusoft]

I would recommend this great library:
https://github.com/Yonaba/Jumper

I wrote about it with some examples:
https://ambience.sk/simple-pathfinding- ... -lua-love/

If you need to take object height in account then you would have to extend the library by your custom code (e.g. if enemy can spot player with a large box in path).

[MisterImpossible]

Thanks for all the replies, everyone, there's definitely plenty for me to get my teeth into.

I'll try and keep you posted if I manage to crack it.

Thanks again.