Grid Pathfinding

As an exercise, I'm trying to learn how the devs of FTL: Faster Than Light did their pathfinding.

I've been using rexrainbow 's plugins to try to get this working, but after trying out the Layout2Board, MoveTo and the Monopoly plugins, but can't quite get what I want.

I feel that using the mentioned plugins, I could manually create a map and do the movement, but I can't figure out how to get it to avoid passing through walls. I feel I could manually choose tile by tile those that are solid (not that I can actually get similar working), but in FTL, where the grid is, say, 32px x 32px, the walls are mere pixels. I fear using this/these plugin(s), I would have to set entire tiles as solids/obstacles.

Note how the characters will avoid walking through the walls, but how thin the walls are. This is what I can't figure out.

If anyone has any ideas, it would be great!

I think you can use a different (invisible) tilemap for pathfinding with half-size tiles, like this:

dop2000 Using Rex's plugins?

I had already tried such an approach using the default pathfinding plugin along with the EasyStar plugin. I get the best results with the default plugin, but because the walls are so thin, at times the character just walks through the walls, or gets stuck, or refuses to stand on the destination point, which is why I'm hoping to do it using a grid based system.

I also find Rex's plugin (while superb) rather cumbersome, in the sense that I have to have 3 plugins all active at once (Board, Square and MoveTo).

I can see the potential, but worry about the process.

I haven't used rex's plugin and don't know how it works.

If you make a seconds tilemap like in the picture I posted, the walls will not be thin. You basically replicate all the walls in this tilemap.

And then I guess you can use the standard pathfinding plugin.

dop2000 At the moment, my walls are 2/3 times larger than FTL's, and either the objects struggle to get through, or they phase through the walls. The pathfinding plugins seemingly don't have an issue with corner cutting either, which is really annoying.

I think you are missing my point. What I suggest is to make another tilemap with thick tiles (1/2 size of the main ship tiles) that will act like walls for the pathfinder plugin.

See this demo I made:

https://www.dropbox.com/s/isnc7nm26ekdv ... .capx?dl=0

You can experiment with pathfinder properties (cell size, speed etc).

Also, after the character has arrived to the destination tile of the ship, you can adjust its position (move to the center of the tile) with MoveTo.

What they did was probably pretty simple. Each grid was a node and nodes separated by a wall weren’t connected.

So then it was just a connected mesh of nodes that the path finding was done on.

I guess what I propose is to do the path finding with events. You can look at any of my astar pathfinding example capx floating around the forum. The only thing that differs from any of them, wether they are on a square grid, hex grid, mesh or even with thin walls between nodes, is how neighboring nodes are picked.

Or instead of just using those capx you can look at the red blob games blog. It has fantastic interactive tutorials for doing pathfinding algorithms.

Why cant you just make your own set of paths, perhaps using Rex's spline.

The layout is not that big, so the number of paths wouldn't need to be that high.

If you are familiar with Rex's pathfinding plugins you can use his "Edge" plugin in conjunction with his pathfinding plugins to create impassible walls/edges.

https://c2rexplugins.weebly.com/rex_board_edge.html

For my Kairosoft type game i'm working on i used the method R0J0hound describes where i did my own with events where each tile has a token list of the neighbour tiles it connects to so people can only walk on the roads. This is good because it means i can also do things like teleporters since tiles can have neighbours they are not physically next to.

Guys, I don't understand - what's wrong with using a tilemap and the default pathfinding (as in the link I posted above)?

It doesn't require any external plugins or any complex programming. And the character is moving more naturally, not like a robot in square angles. Or you can use pathfinding just to generate path and move the character from node to node with MoveTo or some other method.

Nothing I suppose. It’s just an alternate way to do it. Personally I don’t use plugins/behaviors as much since they don’t do exactly what I want most of the time. I just find it more painless to just implement it from scratch instead of bending a behavior to my will.

I think you are missing my point. What I suggest is to make another tilemap with thick tiles (1/2 size of the main ship tiles) that will act like walls for the pathfinder plugin.

See this demo I made:

https://www.dropbox.com/s/isnc7nm26ekdv ... .capx?dl=0

You can experiment with pathfinder properties (cell size, speed etc).

Also, after the character has arrived to the destination tile of the ship, you can adjust its position (move to the center of the tile) with MoveTo.

Ah yeah, I understood what you were saying, but I've already tried that and it caused unusual things.

My character sprite was 16px X 16px, and the gap it was trying to walk through was about 32px. While it would navigate quite well, sometimes it would just cut corners and walk through the walls, no matter how small or large I made the cell size. Even in your example I'm seeing the character walk into the walls you've set up, or cutting corners. It also bothers me that the character will stop too early, and the only way to get him to stand exactly on the square I want is to slide him onto it at the end.

I wanted grid based for more precision. In my grid tests, the character moves great, and ends up exactly in the middle of the room he's meant to walk to. The problem is that he doesn't give a damn about walls at all <img src="{SMILIES_PATH}/icon_e_smile.gif" alt=":)" title="Smile">

mOOnpunk Eep, that looks complex! I'm not enjoying using Rex's plugin(s) at the moment, because I have to use 3 or 4 just to get characters to walk around. I want players to always pick the fastest route, so giving tiles costs would be the best thing.

newt I could use a spline path, but again, if a room is on fire, I'd like for them to be able to walk around it if it's avoidable. Never used splines before, so not sure if that's possible, having people avoid areas if it's dangerous.

R0J0hound I've been looking for examples for the past day or so, but am yet to find anything of yours. Will look harder.

The EasyStar example looks good, but when I use it, my character won't walk around the ship at all, but will happily walk on the outside.

Again, that's why I think grid based is best for me.

Shame there's not a simple plugin/behaviour this late in C2's lifetime.

Here’s the latest one. There are other older ones.

It’s not really a shame. It seems there is a lot of differing requirements for pathfinding that can’t be wrapped up in one plugin.

AnD4D

Even that it sounds like you looking for something very specific and I'm sure that this is not what you want I couldn't resist to try it

https://www.dropbox.com/s/pgvuvd0ijtwy1tp/SpaceShip%20PathFinder2.capx?dl=0

To avoid the collisions checks you can use MoveTo >>>On Hit Target >>Pick Nearest selected Tile >> set selected to False and so on

And on this two Places, I'm not sure if you needed to move on diagonals or to avoid those Grey pictures so I add one Blue square Tile on each to stop the diagonals, you can remove them if you don't need them

This is With the MoveTo Behaviour

https://www.dropbox.com/s/ou6o7jppmwk1vua/SpaceShip%20PathFinder%28MoveTo%29%20Behaivor.capx?dl=0

Guys, I don't understand - what's wrong with using a tilemap and the default pathfinding (as in the link I posted above)?

It doesn't require any external plugins or any complex programming. And the character is moving more naturally, not like a robot in square angles. Or you can use pathfinding just to generate path and move the character from node to node with MoveTo or some other method.

I think if I combine the default pathfinding plugin with Rex's MoveTo plugin, I can use the generated nodes to create the movement I'm looking for. I don't mind the snappy turns.