# Pathfinding on a 2d grid for tower defence

This topic is 621 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## 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 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 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 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):

Edited by spdr870

1. 1
Rutin
44
2. 2
3. 3
4. 4
5. 5

• 11
• 9
• 12
• 10
• 13
• ### Forum Statistics

• Total Topics
632983
• Total Posts
3009714
• ### Who's Online (See full list)

There are no registered users currently online

×