- Joined
- Jul 10, 2006
- Messages
- 3,315
I'm making a tower defense with a randomised path, which is currently accomplished using a random walk that terminates on contact with the map bound.
It sometimes generates a nice path, but I have these issues:
- Path shapes and sizes vary wildly. One path might be a straight shot to the finish, while another might fill up most of the available area. This massive potential difference in size and shape can hurt the balance of the game, since a longer path allows more attack time for your towers.
- Starting at the center of the map, the path typically goes off to one side and leaves the rest of the map empty.
I have a few ideas I haven't tried yet (weighting map areas, direction bias, path distance limit), but I'm wondering if anyone else has any experience making such a algorithm, and if there are better ways to do this.
What I'm aiming for:
- Multiple paths (for multiple players) that meet in the middle, or branch off a bit further away.
- Path shape should fill 40-60% of the available area.
- Depending on whether I use waypoints or a simple attack-move to the center of the map, the path should either have some intersections or none at all.
This is what I consider a "nice" path:
The 9 generated before this one were about a third of the size, going straight for the exit. And as nice as this one is, the bottom right of the map is completely unused.
EDIT: I've more or less solved the length problem by simply restarting the process if the length isn't within a desired range.
Now I think I'll just randomise the start point a bit.
EDIT2:
Made the paths a tile thinner, increased the path segment size variance, and set the start location to random instead of 0, 0.
Takes 5-10 attempts on average, which can easily be done within the first second or two of the game (need to use timers since it often goes over op limit)
Good enough for me
Next up: Set start location to one of the sides, so that the path will be a bounds-to-bounds path.
It sometimes generates a nice path, but I have these issues:
- Path shapes and sizes vary wildly. One path might be a straight shot to the finish, while another might fill up most of the available area. This massive potential difference in size and shape can hurt the balance of the game, since a longer path allows more attack time for your towers.
- Starting at the center of the map, the path typically goes off to one side and leaves the rest of the map empty.
I have a few ideas I haven't tried yet (weighting map areas, direction bias, path distance limit), but I'm wondering if anyone else has any experience making such a algorithm, and if there are better ways to do this.
What I'm aiming for:
- Multiple paths (for multiple players) that meet in the middle, or branch off a bit further away.
- Path shape should fill 40-60% of the available area.
- Depending on whether I use waypoints or a simple attack-move to the center of the map, the path should either have some intersections or none at all.
This is what I consider a "nice" path:
The 9 generated before this one were about a third of the size, going straight for the exit. And as nice as this one is, the bottom right of the map is completely unused.
EDIT: I've more or less solved the length problem by simply restarting the process if the length isn't within a desired range.
Now I think I'll just randomise the start point a bit.
EDIT2:
Made the paths a tile thinner, increased the path segment size variance, and set the start location to random instead of 0, 0.
Takes 5-10 attempts on average, which can easily be done within the first second or two of the game (need to use timers since it often goes over op limit)
Good enough for me
Next up: Set start location to one of the sides, so that the path will be a bounds-to-bounds path.
Attachments
Last edited:
