Hello all!
I’m working on a simple board game where players place fences on a grid, and try to enclose areas. I’ve been stumped for awhile on how lua can detect whether a player’s fence forms a closed loop. I’ve looked up Jordan loops and point-in-polygon theory. I’ve also tried finding code examples for simple versions of the classic “dots and boxes” game. Haven’t yet found anything that will help solve this riddle.
Thanks a bunch!
-Jeff
Hi.
Do you only need to detect that such a loop occurred? Or also trace the path, say for some kind of graphical effect?
In the first case, I can think of a couple approaches.
One is to maintain an adjacency matrix, take the nth power of that (where n = 1 + number of edges, I believe), and then see if there are any non-0 elements on the diagonal.
You might also try a flood fill (there are some topics in the forum, I believe, or the Code Exchange), adapted to only follow edges, and stop if you run across the same vertex twice. (This is basically the DFS approach outlined here.)
From there you can probably trace the path fairly easily, or convert it to something amenable to a path-finding algorithm. (You’d have to decide whether you care, in the situation where more than one loop shows up.)
If you’re especially brave, I do have code for loops, though it’s may not be what you’re after. It’s written for something along the lines of Pepper II or Amidar, where the level is mostly static, but more than a few things rebuild the scene on the fly and it doesn’t seem to suffer. (You can ignore anything about dots and shapes, and probably most if not all stuff about direction.)
StarCrunch
Thanks so much for your thorough reply! Lots of interesting stuff for me to look at. I think that looking at your code triggered the idea that I needed for my own program. I just need to look at each individual tile, and then see if a certain player’s fence can be found in all four directions of that tile.
Thanks again,
Jeff
Hi.
Do you only need to detect that such a loop occurred? Or also trace the path, say for some kind of graphical effect?
In the first case, I can think of a couple approaches.
One is to maintain an adjacency matrix, take the nth power of that (where n = 1 + number of edges, I believe), and then see if there are any non-0 elements on the diagonal.
You might also try a flood fill (there are some topics in the forum, I believe, or the Code Exchange), adapted to only follow edges, and stop if you run across the same vertex twice. (This is basically the DFS approach outlined here.)
From there you can probably trace the path fairly easily, or convert it to something amenable to a path-finding algorithm. (You’d have to decide whether you care, in the situation where more than one loop shows up.)
If you’re especially brave, I do have code for loops, though it’s may not be what you’re after. It’s written for something along the lines of Pepper II or Amidar, where the level is mostly static, but more than a few things rebuild the scene on the fly and it doesn’t seem to suffer. (You can ignore anything about dots and shapes, and probably most if not all stuff about direction.)
StarCrunch
Thanks so much for your thorough reply! Lots of interesting stuff for me to look at. I think that looking at your code triggered the idea that I needed for my own program. I just need to look at each individual tile, and then see if a certain player’s fence can be found in all four directions of that tile.
Thanks again,
Jeff