Jump to content
  • Advertisement
Sign in to follow this  
dendrite

Pathfinding on a 2d grid for tower defence

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

If you intended to correct an error in the post then please contact us.

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
Advertisement

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

Edited by spdr870

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!