Tower Defense pathfinding?

Newbie & Debugging Questions
#1

Hey guys, i’m working on a small tower defense game using LibGDX. I’m probably going to put an android port on the play store.

So, the game is coming along pretty nicely so far. I’m just trying to figure out the best pathfinding method…I was thinking of using A* but I think that may be a little much for what I need…

I started the project using a multidimensional array for the map, but i’m now thinking of switching to using tiled so it is easier to manage larger maps…I don’t know if there is another way to do it using tiled, I do know I was having trouble using the A* method with tiled…

Basically, the enemies will follow a path from A to B…I could define waypoints, but it seems like there could be an issue with enemies running into each other, etc.

Any suggestions or tips?

#2

They literally have paths drawn out in files as waypoints.

#3

What do you mean? Who does?

#4

@Bassex96

My suggestion would be to do this every frame:

check if entities are blocking your path
determine a waypoint to target. if this has changed, re-pathfind
start moving

CopyableCougar4

#5

That’s what I’m going for. Just trying to figure out the best way to calculate the pathfinding…there aren’t many obstacles and it’s just from A to B, so I feel like a* might be too much…

This is the first time I’ve ever done any type of pathfinding.

#6

Try reading this

#7

I think A* would be the best option, for your problem, as it is a grid-based and A* is good with determining the next step.

CopyableCougar4

#8

That is awesome! Thank you Gibbo. A simple search probably would have found that for me! I didn’t think about searching for tower defense specifics.

I agree, CC. I just needed some reassurance!

I just hope I can stick with this without getting bored. I’m only developing it for the experience, but I need to finish something completely so I can move forward to the games I have been planning for months.

#9

That website has way more than just that one article, have a look at the intro to a*. It is a good read.

#10

Yeah, there is some good stuff on there! Thanks.

I’m rewriting this now to use tiled instead…It’s too hard to manage in the array…My question is, how do I set up a grid to use a* with tiled? I tried this before and was unsuccessful. That’s part of the reason, I decided to do it from scratch as I would already have a grid…I know it’s something simple, but I don’t see it.

#11

Whoa, very nice link. This method is almost identical to the method I use in Retro-Pixel Castles. Very nice to have a visualizeable reference next time someone asks me how my pathfinding works. :smiley:

#12

Represent both the map and your graph as a 2D array, use the center of the tile as the origin for positioning.

Simple have each tile represent a node in the graph.

So for instance, you have a wall tile at x = 4 and y = 6. This can be a blocked mode that is not valid for visiting.

The way I do it is create a 2D tile array and a 2D boolean array, as you iterate to generate your map, also grab the tiles block field and fire that it in the 2D boolean array.

All done, now pass it to your node map and use it to generate nodes.

This is the quick way, in reality every have needs custom path finding if you want to add things like weighted edges, move values etc.