Log In  

Cart #55795 | 2018-08-28 | Code ▽ | Embed ▽ | License: CC4-BY-NC-SA

This is something that has been impossible for me to do - until now.

I always wanted to try and make what years ago I labeled as a "Scatter Maze."

That is, a screen full of random lines but done in such a way that all points could be reached around them.

Back on the Apple ][, I used horizontal and vertical lines intersecting each other, but at the time (I was 12) my brain couldn't fathom how to make certain it was possible to draw these lines and guarantee a path around them.

So - the monsters would hit the wall and start chewing. :) So - once you fought the monster, you could use the hole he munched through the wall to get you to get to the other parts of the dungeon. Not the best solution, but it worked.

Later I realized it could be done but I would need a VERY fast fill routine to even come close to exploring this idea.

And - here it is. No, it's not very fast but it's fast enough. Guaranteed to always leave a path to all points despite the random placement of walls. I set it so all vectors appear on a tight grid. If you want the freedom of all points and any size walls, just change the program to reflect this.

Interesting to watch, might even be useful for someone building a rather chaotic dungeon or something.

And with that, bedtime. Hope you like it !

P#55796 2018-08-27 23:40 ( Edited 2018-08-28 19:36)

Lmao after a couple of passes i feel like i hit a recursive wall of some sort because it started chugging haaard, real slow.

P#55798 2018-08-28 00:11 ( Edited 2018-08-28 09:16)
:: dw817

Yes, it does indeed slow down after a-while. :)

I need to check my code to see if there's any way to optimize and speed it up.

You were mentioning checking for intersection of 2-lines in your last comment. This wouldn't work always as you might have 2-lines intersect making an X and then a line going through the middle.

The check would say this is invalid, when in fact it does not close off an area.

No, I just need to work with it a bit. Give it straight same-distance lines and hard 90 and 45 degree angles.

P#55804 2018-08-28 12:48 ( Edited 2018-08-28 16:48)

No, no I had a different idea in mind, hence why i removed the edit.


Here's an example of what I was talking about. This generates lines and each line generated, recursively checks each line it intersects with as well as each line they intersect with, so that a closed off area is never created, however, this is a "mathematically" correct answer, not a visual one. I would have to add a "scaling/zoom" type function for you to be able to see that in fact, each area is indeed accessible, but I assure you they are. But this is also just completely random with no bias being inflicted towards creating any aesthetically pleasing maze, hence no line length is specified nor any space management employed.

However you are correct, this method will not create areas that overlap such as you specified.

P#55806 2018-08-28 13:19 ( Edited 2018-08-28 17:21)
:: dw817

Morning, CD:

  • No, I'm definitely seeing closed off areas.
P#55807 2018-08-28 13:31 ( Edited 2018-08-28 17:31)
:: dw817

Cart #55809 | 2018-08-28 | Code ▽ | Embed ▽ | No License

Here is mine updated.

Hold (O) to draw (no check for close-offs, speedy)
Tap (X) to fix closed off spots. Hold to check and continue normally.

Also the walls are now straight 90 degree lines or 45-degree lines, and are all the same length.

Adds a bit of uniformity to the set.

P#55808 2018-08-28 13:34 ( Edited 2018-08-28 17:38)

Those aren't closed off, like I said, if you could zoom you'd see the areas between. Take for instance the green and maroon lines down at the bottom, they do not form a closed off area, the resolution is just poor such that you cannot tell. I'll try to do a rough mspaint of what i mean.

The lines "mathematically" are infinitely thin, so depending on your resolution they will appear to have closed areas, even in the paint version, the "thickness" of the line makes it seem, as I circled, as there are closed off spaces, but if the lines were drawn as pure vectors, think flash, you could continue zooming infinitely and no closed space would exist, down to the point of contact.

The others are a little messier, but they are indeed the same issue. When I get some free time tomorrow, I'll work on a version of this where zooming is possible so you can indeed see that purely there is no closed space.

Although I must restate, this is just from a maths point of view, when you get down to rendering and actually displaying the lines, you have to have some code to clean things like that up, by either eliminating all lines that don't hold a certain slope differential towards each other, or cheating and pushing some pixels around a bit so the lines look cleaner but are slightly different than when first generated.

A second example:

The last one you circled gets even weirder because if lines share some points they get painted over and i didn't mess with any color blending.

P#55812 2018-08-28 14:52 ( Edited 2018-08-28 18:56)
:: dw817

Well ... Hmm ... How about where it VISIBLY is closed off - available to the naked eye without enlargement.

Visibility of non-closed off areas is what we're shooting for here.

P#55813 2018-08-28 15:36 ( Edited 2018-08-28 19:36)

[Please log in to post a comment]

Follow Lexaloffle:        
Generated 2020-08-08 09:21 | 0.021s | 4194k | Q:44