2
$\begingroup$

Assuming a 2D maze, how would one go about solving it for rigid 2D object moving through it?

Additional specification:

  1. The object shape - it is a single entity, not a swarm/fleet. A shape of something one could cut out of cardboard, no infinite areas, no infinitely asymptotic corners. The shape and size relative to maze is fixed.
  2. The object movement - it can move as a cardboard shape would without leaving its plane. Continuous movement in any direction, no jumps through space. Rotate around any point in plane as one would rotate cardboard shape without lifting it off plane. Can move and rotate simultaneously.
  3. The maze is fixed in size relative to object. The maze does not change as the object moves through it and does not interact with object in any way apart from not allowing any part of object to move through maze walls.
  4. The maze is finite.
  5. The maze is represented as a set of straight lines in 2D space. No curves, as those can be approximated with many straight lines. The data structure is irrelevant, should be translatable to any other data structure. Can assume non-zero maze wall thickness if that is relevant to answer.
  6. The maze can contain loops through which object can pass through. Can contain loops that allow a smaller object to pass but not the one we need.
  7. The maze has one entrance and N>0 exits although I think any algorithm that can find a path to exit should also be able to identify if a path does not exist.
  8. The goal is to find any one path from entrance to exit that the object can move through

P.S. If there is existing literature on this, please add it in comments or answers as I might have used the wrong keywords and could not find it.

$\endgroup$
1
  • $\begingroup$ Assuming the shape of navigator is convex? Assuming the movement of navigator is rotation+translation? $\endgroup$ – Apiwat Chantawibul Oct 2 '19 at 10:45

Your Answer

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

Browse other questions tagged or ask your own question.