Sign in to follow this  

Pathfinding on a 2d grid for tower defence

Recommended Posts

I'm working on a small tower defence project. The board is a 2d grid.

I used BFS to compute paths between the enemy's spawn location and its destination, so I have a list of coordinates that looks something like this:
(9, 0), (8, 0), ..., (0, 0), (0, 1), (0, 2), (0, 3), (1, 3)

Enemy coordinates are floating point, since I need to simulate movement across a square taking some time. The way I'm currently doing it is to compute the direction between the current square the enemy is on, and the next square on the path, then having the enemy move in that direction. For e.g, (9, 0), (8.9, 0), (8.8, 0), ...

However, this doesn't work well when the enemy is turning a corner. In this case, after moving west from (9, 0) to (0.9, 0), it moves north to (0.9, 3.1), then east to (1, 3.1).

I need each enemy to spend the same amount of time in each square, not make turns like this. It looks like if I can make them stay in the centre of the square, that would solve my problem. How can I do so?

Share this post


Link to post
Share on other sites

Don't store the current position of enemies as floating point.  Instead, store this:

  • Previous tile position (int x, int y)
  • Next tile position (int x, int y)
  • Progress (float in range 0.0-1.0)

Each frame, increase the progress value.  When progress hits 1.0, set progress to 0.0, set previous tile position to next tile position, and calculate a new next tile position.  For rendering, calculate current position as (next_position * progress) + (prev_position * (1.0 - progress)).

 

 

Alternate approach: define the center of the tile at (x, y) as (x + 0.5, y + 0.5).  Therefore an enemy is vertically centered if (y - 0.5) is an integer and horizontally centered if (x - 0.5) is an integer.  Enemies can only change direction if they are both vertically and horizontally centered.  But, you need to make sure that you actually hit the center instead going past it.

Share this post


Link to post
Share on other sites

Wow, I really like the first solution for its elegance. I had something like your second solution, in mind, but thats harder to understand and implement right. Many thanks.

Share this post


Link to post
Share on other sites

I am currently building a tower defense game myself. The movement of the enemy units uses the following techniques:

- flowfields pathfinding (long range)

- a* pathfinding (short range)

- predictive steering (for natural movement and cornering)

 

Flowfields allow for high performance, a* allows for flexibility. You can search on google for those techniques. I can help if you have specific questions.

 

You can see the AI with debugging info in this short video (note that the units do not take the shortest path, but try to avoid towers):

https://www.youtube.com/watch?v=ss4hzj1WC_4

Edited by spdr870

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this