Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Fast maze check
#1
So, what is the fastest / most simple way to check if a path is invalid or a combination does not need to be checked?
Best i´ve come up with so far is "check if a vertical line is directly or indirectly blocked". of course neither does suffice nor is fast enough...
Anyone got some good ideas?
Also, whats the least bits one could represent the walls in an UC in?
One bit per normal tile is too much kinda... >_>
SNAAAAAAP, do stuff! I broke it again...
Reply
#2
Checking if at least 1 of a start, end, and all letters are touching the same open area provides a strong candidate for valid path. Add in teleports for perfect. Order of path doesn't matter for valid path request.

Perhaps valid path between start and end only for quick invalid checks. Are you wanting a "always correct" validation, or "when condition fails, always invalid, but passing condition doesn't mean successful validation."? Vertical check certainly provides the latter.

In a 3d sudoku solver, I was using 9 bits per cell (729 cells). It sounds like you are already more efficient then length*width bits, being at used wall bits instead. This true?
Reply
#3
well the evaluation of "touch same area" is too expensive. in theory i could do a flood fill using all WPs+start/end, but that might only pay off for an UC, and even there probably not. (the actual way finding is more or less a flood fill, only executed once per wp/tp, but just til found in good case)
gonna try that though, lets see what happens.
what i´d need is a very simple way of checking only a fraction of the tiles and knowing i don't need to test this maze, since its definately not a valid path. but that may probably not be possible.
The best thing i could imagine would be a way to know which tiles in an already existing maze definately must not be blocked, so i could ignore those combinations completely. Problem with that being, the only way i´d know how to do so is blocking them and trying to find the path...

as for the storing, i tried one bit per normal tile (wall or not wall), one after another, so i could store an UC combination in like 300bit, since that ignores rocks/wps/etc.
problem being, thats still one 64bit pointer plus 6*64bit value, which is way too much to store even some 100mio combinations.

anyone ever tried a solver with neuronal nets? that´d probably be cool, even if it fails... yet i´ve never done anything with that...
SNAAAAAAP, do stuff! I broke it again...
Reply
#4
I'm still on the wrong side of your question with this:
From a trunk (valid maze with any % of walls already placed), know a valid walking path. If a new wall is on that path, consider the spot just before and just after as points 1 and 2. If you can travel between 1 and 2, you still have a valid maze. Alas, this is still a "invalid test doesn't mean invalid maze" idea. Sad

(03-25-2014, 08:54 PM)TheCurse Wrote: The best thing i could imagine would be a way to know which tiles in an already existing maze definately must not be blocked, so i could ignore those combinations completely.
For each open cell, if it has exactly 1 or 2 open sides (and if those two sides share a common corner piece, it must be solid), mark the square as a corridor. With a flood fill, each walking flood cell needs to recall which corridors it has passed though. If two walking flood cells join that have different corridor parents, the corridors in question are not unique path corridors. The other corridors should be the would block path corridors.


Silly thoughts, likely not valuable:
http://pastebin.com/tDw310hR
Reply
#5
(03-25-2014, 10:34 PM)Aki Wrote: I'm still on the wrong side of your question with this:
From a trunk (valid maze with any % of walls already placed), know a valid walking path. If a new wall is on that path, consider the spot just before and just after as points 1 and 2. If you can travel between 1 and 2, you still have a valid maze. Alas, this is still a "invalid test doesn't mean invalid maze" idea. Sad
that would mean in "bad" case, i´d travel through the whole remaining maze again. is kinda similar to a possible (and not that easy) improvement of the path finding i´ve been wanting to try for a long time now.

that corridor idea is not that trivial to implement, but it looks like a good way... Smile
need to put some thought into that...
that pastebin idea looks most interesting though. a simple "give the value to neighbor" probably won't do, but i think there might be something... Big Grin
SNAAAAAAP, do stuff! I broke it again...
Reply
#6
Hey ReCurse,

My youngest brother started something using Neural Networking, but he had to take a break from it. I went to dinner with the family last night and he mentioned that sometime soon he wants to get back at it...I assume he made relatively little progress on it...
Reply
#7
(03-25-2014, 10:34 PM)Aki Wrote: For each open cell, if it has exactly 1 or 2 open sides (and if those two sides share a common corner piece, it must be solid), mark the square as a corridor. With a flood fill, each walking flood cell needs to recall which corridors it has passed though. If two walking flood cells join that have different corridor parents, the corridors in question are not unique path corridors. The other corridors should be the would block path corridors.
The shadow block on this image is not a corridor, but is a blocked path location. This quoted idea won't find all of the "don't block this" locations.[Image: 2014.03.26.Pathery.jpg]

For efficiency of a solver, if dead ends can be identified and marked as doesn't matter to a flooder, less work would be done. Not a simple project for not very much gain.

Further, there are corridors with unique paths that are allowed to be blocked due to no way-points though it's passage. I suppose the original idea needs modified to note unique corridors are only consider no blocks when the flooder reaches an exit way-point, baring teleports.
Reply
#8
oh ye that too... D:
its not for the flooder not to fill, but its for not placing a block on it.
if i have a path i take each wall and put it on each tile of the path looking for improvements. so every tile i can rule out is [wallCount] less checks...
SNAAAAAAP, do stuff! I broke it again...
Reply
#9
For any two adjacent squares on the map, if a flood-fill on either side never touches a checkpoint, a start/finish, or a tele-out, none of those squares (excluding the two we started with) are part of any shortest path.

And since only walls on the shortest path can affect the path, that means the best solution will never include any of those squares.
Reply
#10
that part is covered already since (except in the beginning) i only place walls on the existing path (recalculating after i took out a wall).
well, since some time i implemented a check that says "if a tile is blocking and has only 2 (or less) adjectant tiles (or more but they only are connected to this tile), then they are blocking too.". this is done iteratively as long as the connected tiles are blocking.
probably only really pays off for UC and unlimited, but its a not that expensive check and seems to do its job. Smile
SNAAAAAAP, do stuff! I broke it again...
Reply


Forum Jump:


Users browsing this thread: 1 Guest(s)