2

I want to model a maze.

I want to avoid using a matrix in which each cell has four walls (which I could easily do using a two-dimensional array where each cell contains up to four walls) because I don't want the complication of managing the bi-directional relationship with neighboring

I understand that using a graph can potentially help. (I have read this question, which suggests using a graph, and I have tried reading up on graph theory a little, but the practical implementation thereof eludes me).

Can you provide a simple to understand explanation of how to model a maze using a graph? (The language is not important; I would like to understand the concept).

Community
  • 1
  • 1
mydoghasworms
  • 18,233
  • 11
  • 61
  • 95
  • In your array (of numbers?) can't you just take "0" to mean "empty" and "1" to mean "wall"? – BretC Jan 29 '15 at 10:43
  • Array[n,n] of array[4] (four walls by cell) – Typo Jan 29 '15 at 10:45
  • possible duplicate of [Data Structure to Represent a Maze](http://stackoverflow.com/questions/4551575/data-structure-to-represent-a-maze) – Typo Jan 29 '15 at 10:53
  • @Bret , each cell has four walls. But if I have four walls in each cell, it means I must maintain a bi-directional relationship. – mydoghasworms Jan 29 '15 at 11:17
  • @Typo, please see my reply to Bret! Also I explained it in the question. I even referred to the question you are suggesting as duplicate and I think it is implicit that my question is different, because I am asking, if graph is the solution, for an example. – mydoghasworms Jan 29 '15 at 11:18
  • @Typo I have highlighted the portion of the question where I am asking for an example, so you can see it is not duplicate, if you read both questions carefully. – mydoghasworms Jan 29 '15 at 11:24
  • mydoghasworms You potentially have four walls by cell, as stated by @Bret you can logically represent the existence of each one by value (i.e. 0 = no wall, 1 = wall, 2 = open corridor, etc.). As for the duplicate, you made the same question asking for another answer. – Typo Jan 29 '15 at 19:33
  • @Typo: Sigh. OK, I am going to rephrase the question completely. BTW, if each cell has 4 walls, remember that it shares that wall with up to 4 neighbors. If you take down one wall in the cell but not the same wall in the corresponding cell, you end up with a problem, you understand? – mydoghasworms Jan 30 '15 at 04:45
  • Let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/69870/discussion-between-mydoghasworms-and-typo). – mydoghasworms Jan 30 '15 at 04:53

0 Answers0