Alex Rivera | Logout

Generating a tower defense maze (longest maze with limited walls) - near-optimal heuristic?

Asked 2012-04-26T17:03:24.817
50

In a tower defense game, you have an NxM grid with a start, a finish, and a number of walls.

Image1

Enemies take the shortest path from start to finish without passing through any walls (they aren't usually constrained to the grid, but for simplicity's sake let's say they are. In either case, they can't move through diagonal "holes")

Image2

The problem (for this question at least) is to place up to K additional walls to maximize the path the enemies have to take. For example, for K=14

Image3

My intuition tells me this problem is NP-hard if (as I'm hoping to do) we generalize this to include waypoints that must be visited before moving to the finish, and possibly also without waypoints.

But, are there any decent heuristics out there for near-optimal solutions?

[Edit] I have posted a related question here.

algorithm path-finding heuristics maze
Edit
Report

1 Answer

1

I have no idea if this would work, because you could make new islands using your points. but it could help work out where to put walls.

I suggest using a modified breadth first search with a K-length priority queue tracking the best K paths between each island.

i would, for every island of connected walls, pretend that it is a light. (a special light that can only send out horizontal and vertical rays of light)

Use ray-tracing to see which other islands the light can hit

say Island1 (i1) hits i2,i3,i4,i5 but doesn't hit i6,i7..

then you would have line(i1,i2), line(i1,i3), line(i1,i4) and line(i1,i5)

Mark the distance of all grid points to be infinity. Set the start point as 0.

Now use breadth first search from the start. Every grid point, mark the distance of that grid point to be the minimum distance of its neighbors.

But.. here is the catch..

every time you get to a grid-point that is on a line() between two islands, Instead of recording the distance as the minimum of its neighbors, you need to make it a priority queue of length K. And record the K shortest paths to that line() from any of the other line()s

This priority queque then stays the same until you get to the next line(), where it aggregates all priority ques going into that point.

answered 2012-05-01T01:45:53.877

Your Answer