# maze

This topic is 5042 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?

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 9
• 31
• 16
• 11
• 10
• ### Forum Statistics

• Total Topics
634118
• Total Posts
3015607
×