Jump to content
  • Advertisement
Sign in to follow this  
nikita

maze

This topic is 4945 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'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 this post


Link to post
Share on other sites
Advertisement

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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by WeirdoFu
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?



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 this post


Link to post
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 this post


Link to post
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 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!