0
\$\begingroup\$

I am new to algorithms but currently creating a little game with the need for some.

I have a 2d grid/board with a start and a finish field. Between those two fields are several platforms which can be entered. Each platform has a counter on it. When going on a platform the counter is decreased by one. If the counter reaches zero the platform is gone. The goal is to go to the finish field AND destroy every platform field. A little exmaple:

0 1 0
1 2 1
1 0 F
S 0 0

S being the Start field and F being the finish field the right path would be going UP, UP, RIGHT, UP, DOWN, RIGHT, DOWN.

All I could find so far were algorithms getting paths for mazes without counter. Do you have any tips for a algorithm that can decide, if the current maze if solvable or not and maybe even get the correct path?

Thanks in advance!

\$\endgroup\$
  • \$\begingroup\$ An algorithm that can check your mazes would also be able to solve certain Hamiltonian Path Problems as a special case (all nodes wither 0 or 1), and that type of problem is notoriously tricky (NP-Complete), so randomly generating & checking mazes is likely to be more laborious than you want. Ensuring your generation method itself creates solvable mazes by construction, as in RobM's answer, avoids this complication. \$\endgroup\$ – DMGregory Oct 3 '16 at 11:11
1
\$\begingroup\$

One way would be to auto generate the maze by coding your own 'maze generation bot'. This would have the nice advantage of being quicker as you would not having to do them manualy. As well as knowing that it would always be solveable.

So the sequence of events for maze generation would be this.. Create an empty map, full of zero's pick random coord for 'S'. Pick random coord for 'F'. Put the bot on the 'S'

repeat:

pick a random direction ( up/down/left/right )

check the direction is within map coord and wont lead to an 'S'

Move the bot.

if the cell is 'f then end

otherwise increment the gridcell

repeat until 'f' is reached

You may have to run this a few times. As the bot could potentially create a 100 step sequence. So run it a few times and pick the one with an appropriate amount of steps depending on how difficult you need it to be.

So you may auto create 1st 10 maps with 6-12 steps the next 10 use 12-18 steps etc etc

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.