# maze

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

## Recommended Posts

i've a question about the following task: given is a maze (it's a simplified pacman-game) which contains several pills (and powerpills). now the goal is to write a program which is to find a path to eat all pills in the maze (while the path should be as short as possible). what would be a good strategy? thx

##### Share on other sites

Simple:

Use A* to go to the nearest pill, from there go the the nearest other pill etc...

Hard:

Sounds like a traveling salesman problem. Google.

Edo

##### Share on other sites
Quote:
 Simple:Use A* to go to the nearest pill, from there go the the nearest other pill etc...

that seems to be a greedy-algorithm.

and yeah it sounds like a traveling salesman problem.

i should mention that the execute time limit is 30 seconds. it doesn't matter if you need the whole 30 seconds or just 2. Therefore it would be possible to use an algorithm which is not perfectly fast. the maximum dimension of the maze is also just 40x40 (very small).

##### Share on other sites
Now, when you say that the execution time is 30 seconds, does that mean just the path finding? or does that include everything else?

Do you create the path first? or create it on the fly?

##### Share on other sites
Yeah, it does look like its going to be a special case of the travelling salesman problem. There's just going to be quite alot of overlapping going on.

You'll probably need something slightly more complicated than A*.

##### Share on other sites
Quote:
 Original post by WeirdoFuNow, when you say that the execution time is 30 seconds, does that mean just the path finding? or does that include everything else? Do you create the path first? or create it on the fly?

i should explain that:

given is a maze (text-file) and the program must find a path (however you do that). after maximum 30 seconds the program is to output a path (in a outputfile). it's not a live-time interaction; it's a static problem.

##### Share on other sites
Here's how you might formulate the problem.

You will need to create a graph where each of the nodes will be any turn in the path and any crossroad. Actually, just the crossroads will work. So, basically, create a graph with all the forks in the maze as nodes and have a link between any two nodes that have a path between them. Your goal will then be to find a tour that crosses every link at least once. The length of each link will be defined by how many pellets occupy or can occupy that path.

As for solving it....that I'm still thinking about. :p

##### Share on other sites
it's important that i need not an algorithm which finds always the optimal solution (but it would be fine if there is one) but a good solution (that includes heuristic methods)

[Edited by - nikita on March 31, 2005 2:57:25 AM]

##### Share on other sites
How many is a 'few'?

(i've got an idea. But it all depends on how many things there are to search.)

From,
Nice coder

##### Share on other sites
well, for a 40x40 maze, I'd guess you wouldn't have more than 30 or 40 intersections. Is that a small enough number to brute-force TSP?

##### Share on other sites
Depends on the connectivity, but probably not.

Look into ant colony optimization and or ant systems, but ant colony will be better, since it was designed to solve problems like this, especially if optimality is not required. Since that can't be guaranteed anyways.

##### Share on other sites
Quote:
 Original post by fractoidwell, for a 40x40 maze, I'd guess you wouldn't have more than 30 or 40 intersections. Is that a small enough number to brute-force TSP?

Its not the number of intersections.

Its the number of pills that i need. (you only need to get a path from pill to pill, ect.)

I've got a really sneaky idea.

From,
Nice coder

##### Share on other sites
Use two stacks

1) the visited stack
2) a 'desision' stack that contains alt movements

##### Share on other sites
Quote:
 Original post by fractoidwell, for a 40x40 maze, I'd guess you wouldn't have more than 30 or 40 intersections. Is that a small enough number to brute-force TSP?

Hell no.

40! is HUGE.

We need a sneaky algo.

From,
Nice coder

##### Share on other sites
Quote:
 Original post by Nice CoderHell no.40! is HUGE.We need a sneaky algo.From,Nice coder
Sorry, poor choice of words. I meant use a heuristic-but-relatively-time-consuming-compared-to-greedy algorithm, of the sort on that page. Not just a naieve recursive implementation, which, as you point out, would be fine if you have a quantum computer to run it on. :P

##### Share on other sites
Quote:
Original post by fractoid
Quote:
 Original post by Nice CoderNice coder
Sorry, poor choice of words. I meant use a heuristic-but-relatively-time-consuming-compared-to-greedy algorithm, of the sort on that page. Not just a naieve recursive implementation, which, as you point out, would be fine if you have a quantum computer to run it on. :P

Ok.

I was just getting a WTF moment.

[lol]

From,
Nice coder

##### Share on other sites
Quote:
 Original post by Nice CoderHow many is a 'few'?(i've got an idea. But it all depends on how many things there are to search.)From,Nice coder

what do you mean with "how many is a 'few'"?

##### Share on other sites
How many items are we talking about?
2? 3? 10?

From,
Nice coder

##### Share on other sites
oh,
see http://www.clutter.ch/ex.png; it's a screenshot of a given maze.

##### Share on other sites
Ok. 11 items. (10 pils, one powerpill).

You could get a path in a few miliseconds.

ok 11! = 39,916,800

Which is doable in 30 seconds. (you have 40M nodes to search).

Just as long as it doesn't increase (one more item, and you in the 400Mitem mark. WHich is a little heigh. Two more and your in the billion item mark).

Ok, assuming 1Billion instructions per second.
You have 30 seconds.
So 30billion / 39,916,800 = 751 instructions per node max.

From,
Nice coder

##### Share on other sites
The issue here is not really choosing the next closest pill. The problem with just looking at the pills is that you don't take into the consideration of the topography of the "maz" itself. Yes, choosing the next closest pill in a greedy way may work, but that may mean you have to circle all the way around to get to it, even though you were very close to it, since there could be a wall blocking it. However, in the process of circling around, you would have eating alot of other pills as well, possibly. This is why you consider the topography of the maze instead of just look at the pills. In being able to choose the shortest path to traverse all paths in the maze, you're guaranteed to have eaten all the pills, its as simple as that. If the pills are evenly spaced, then the distance you traverse can then be meassured by the number of pills that can be on the path.

Looking at just the pills may seem like you're simplifying the problem, but all it does is over complicate it computationally. Unless, of course, there are way fewer pills than intersection, which in most pac-man style games is probably a no.

##### Share on other sites
Quote:
 Original post by WeirdoFuIn being able to choose the shortest path to traverse all paths in the maze, you're guaranteed to have eaten all the pills, its as simple as that.

yeah, but how can i find the shortest path - that's my problem.

[Edited by - nikita on March 31, 2005 12:43:46 PM]

##### Share on other sites
Quote:
 Original post by WeirdoFuThe issue here is not really choosing the next closest pill.[...]
It is if you measure distance in the typical graph method (how many nodes away, with a node possibly meaning one 'walkable tile' in this case) rather than the typical physics way (sqrt(dx^2 + dy^2)).

##### Share on other sites
Well, if we look at a pill as a node, then you may have 10 times more nodes than you will need and have a damn hard time processing all of them. Under the assumption that you will get to all pills by traversing all paths at least once reduces the number of nodes that needs to be processed down to just the intersections of the paths.

Even with A* search, you can assign weights to each link individually. No one said the distance between nodes had to be uniform.

For one thing....there will be alot of backtracking involved, that's for sure.

The simplest solution off the top of my head right now is a simple trial and error method that you just keep running for 30 seconds and keep track of the best answer found.

1. Start from a random node/intersection.
2. Probabilistically choose the next node to go to on an untraversed path/link, based on the distance (number of pellets to the next node). You can do this by having the longest paths have higher probability of being chosen or the shortest.
3. Once traverse, mark a link as being traversed.
4. Push the path onto a stack, or just simply the node you came from
5. Repeat steps 2 - 4 until the current node you're at has no more untraversed paths
6. If no more traverable paths at current node, backtrack to the last node visited that still has paths that have not been traversed. Go to step 2.
7. If all paths traversed, then end.

Of course, along the way, you'll have to keep track of the order of the nodes visited, even when backtracking, for that will be your path. You may also choose to keep track of the distance travelled or simply do that at the end when you have the full path.

This should be fairly fast if you code it right. Probably execute it 10 - 100 times a second and always keep track of the best answer found so far. You'll probably not get an optimal solution, but will probably get something pretty good.

##### Share on other sites
Precompute the distances from each pill to each other pill using breadth first search, then use a minimum spanning tree algorithm to find the shortest tree that connects all of the pills (start off at a random pill).