18
|
8000 Views
|
2 Replies
|
19 Total Likes
View groups...
Share
GROUPS:

# Brownian Motion Maze Solving (based on "The Dumbest Way To Solve A Maze")

Posted 2 years ago
 Attachments:
2 Replies
Sort By:
Posted 1 year ago
 Even before the web one could search, there were online database systems that would search it's kind of like how Bluetooth could be pretty useful...a lot of the time we use the power of teamwork and the computation, the graphical capabilities that we've got when we're cracking these chestnuts..what if something new came along...and we didn't get all the simulations represented that we wanted to represent within the Brownian motion that we are portraying, which describes the random movement of particles suspended in a fluid, like graphene. It's a fundamental concept and it honestly looks like the soot, the thermal motion of molecules that, in the context of maze solving, might allow us to repurpose this computational metaphor. We should get a Nobel Prize for what we did with this maze it's the greatest path of all time through this complex structure...where we don't just mesh all these particles together, we can simulate and redo random steps of particles until one reaches an exit point. And this is what we're missing out on, whenever we solve a maze. dims = {8, 4}; hallwayThickness = 0.8; ballCount = 1000; spanningTree = FindSpanningTree[ GridGraph[dims, EdgeWeight -> {_ :> RandomReal[]}] ]; outerRegion = Rectangle[{1, 1} - 1 + hallwayThickness, Reverse[dims] + 1]; wallsRegion = RegionDifference[ RegionDifference[ Rectangle[{1, 1} - 1 + hallwayThickness, Reverse[dims] + 1], RegionDilation[ DiscretizeGraphics[ Line[GraphEmbedding[spanningTree][[#]]] & /@ List @@@ EdgeList[spanningTree]], Rectangle[{0, 0}, {1, 1}*hallwayThickness]]], Rectangle[ {dims[[2]], hallwayThickness}, {dims[[2]], 0} + {hallwayThickness, 1} ] ]; wallMember = RegionMember[wallsRegion]; mazeMember = RegionMember[outerRegion]; initPs = {1 + hallwayThickness/2, dims[[1]] + hallwayThickness/2}; magneticField = -0.05; positionSeries = Module[{ps, vs, magnetEffect}, Monitor[ps = ConstantArray[initPs, ballCount]; Reap[Sow[ps]; While[And @@ mazeMember[ps], vs = RandomPoint[Circle[], ballCount]*0.1; magnetEffect = If[First[#] <= (1 + hallwayThickness/2), {0, magneticField}, {0, 0}] & /@ ps; ps = MapThread[ If[wallMember[#1 + #2 + #3], #1, #1 + #2 + #3] &, {ps, vs, magnetEffect}]; Sow[ps]] ][[2, 1]], Graphics[ {wallsRegion, Orange, PointSize[0.025], Point[ps]}, ImageSize -> Large]]]; winningIndex = FirstPosition[mazeMember@Last@positionSeries, False][[1]] Graphics[{ wallsRegion, Orange, Line[positionSeries[[All, winningIndex]]] }, ImageSize -> Large] Manipulate[Graphics[{wallsRegion, If[i > Length[positionSeries]*2/3, {Red, Thick, Circle[positionSeries[[i, winningIndex]], 0.01], Thin, Blue, Line[positionSeries[[All, winningIndex]]]}, {}], Orange, PointSize[Medium], Point[positionSeries[[i]]]}, ImageSize -> Large], {i, 1, Length[positionSeries], 1} ] ballMaxDistances = Max /@ Total[(Threaded[initPs] - Transpose[positionSeries])^2, {3}]; ballDistanceRanking = Ordering[ballMaxDistances]; Manipulate[ Graphics[{wallsRegion, Orange, Line[positionSeries[[All, ballDistanceRanking[[n]]]]] }, ImageSize -> Large], {n, 1, ballCount, 1}] For the ten million degrees centigrade plasma that has enough particles that they want to undergo fusion, even if you can contain it with some kind of magnetic field...you can reflect the natural process of scientific phenomena including diffusion and pathfinding within this magnetic field, and because of the tree structure it's this maze that is generated without loops, directed and acyclic in that the possibility of a unique path between any two points is predetermined..in that simulation the Brownian motion exists within the confines of the maze walls, and if a particle intersects with a wall it reverses its direction across molecular space to avoid crossing into the wall, thus remaining within the valid paths of the maze...potentially we can Reap and Sow the path of each particle and effectively solve the maze and determine the first particle to reach the exit. It's a slow, steady progress that allows for real-time observation of particles' paths and their distances post-simulation...which is the first particle to reach the threshold beyond the exit? How does the simulation evolve across the time-lapse of the particles' positions or and the temporal progression of the simulation? The metaphor of the pulled string means that even post-simulation the winning path can be optimized, yes vacuum tubes have been developed for many years...while the initial path found may be circuitous it can be refined to a more direct route..which is how we solve optimization problems like the unsupervised spectral clustering that occurs within a dishwasher, or the operations research that we do and I do, I suggest the statistical analysis that shows us the characteristics of the Brownian paths within the maze which might as well be 35 years old and that takes over the things we think about as opposed to say low-level programming languages, which putatively can in that case describe the incumbent characteristics of the Brownian paths within the maze. And that's why we've got this tiny little wheel of computational simulation that allows us to explore computational space to mimic and mirror the most intricate of things..like let's say we want to add padding to the side of a microscopic particle interaction, scenario card or add a table of contents to our model of particle dynamics? I think the collision detection and handling emphasizes the foundation of creativity in that assigning value to something like Bitcoin or mathematical axioms allows us to build our own Brownian motion simulation, a hangout where the question of whether or not we need to redo our underlying rules of particle interaction can be rewritten with a resounding yes, as this vast, interconnected Ruliad concept what with its hypergraphs making up the fabric of hyperspace; it proposes a discrete structure and in the simulation each particle's path through the maze, is discretely determined by the local interactions with the maze walls and other particles, which encapsulates the infrageometry of the Ruliad as a microcosm of the conservation laws when two particles collide - much like the molecules governed by collisions which are elastic...the kinetic energy of the particle system is conserved in this Newtonian cradle where the unpredictable nature of particle dynamics adheres to the physical laws that govern our universe. dims = {10, 14}; hallwayThickness = 1; ballCount = 100; particleRadius = 0.05; timeStep = 0.05; baseOrange = RGBColor[1, 0.5, 0]; colors = Table[ Lighter[baseOrange, RandomReal[{0, 0.5}]], {ballCount}]; initialPosition = {2 + hallwayThickness, dims[[2]] - hallwayThickness - 2}; positions = Table[initialPosition, {ballCount}]; velocities = RandomReal[{-1, 1}, {ballCount, 2}]; paths = Table[{}, {ballCount}]; generateDiagonal[start_, end_, count_] := Module[ { dx = (end[[1]] - start[[1]])/count, dy = (end[[2]] - start[[2]])/count, step }, step = Min[Abs[dx], Abs[dy]]; Table[ { {start[[1]] + i*dx, start[[2]] + i*dy}, {start[[1]] + i*dx + step, start[[2]] + i*dy + step} }, {i, 0, count - 1}] ]; wallCoordinates = { {{3, 3}, {7, 5}}, {{2, 7}, {4, 9}}, {{1.75, 0}, {2, 15}}, {{9.25, 0}, {9.5, 15}}, {{0, 13.25}, {11, 13.5}}, {{0, 1.75}, {8.5, 2}}}; obstacles = Join[ wallCoordinates, generateDiagonal[{8, 4}, {4, 10}, 10] ]; reflectBounceParticleWall[pos_, vel_, obstacles_] := Module[ {newPos = pos, newVel = vel, reflect, minTimeStep = timeStep, xCollision, yCollision}, reflect = False; xCollision = False; yCollision = False; Do[ newPos = pos + vel*timeStep; newPosNew = pos + vel*2*timeStep; newPosNewPos = pos + vel*3*timeStep; If[(pos[[1]] >= obs[[1, 1]] && pos[[1]] <= obs[[2, 1]] && pos[[2]] >= obs[[1, 2]] && pos[[2]] <= obs[[2, 2]] ) || (newPos[[1]] >= obs[[1, 1]] && newPos[[1]] <= obs[[2, 1]] && newPos[[2]] >= obs[[1, 2]] && newPos[[2]] <= obs[[2, 2]] ) || (newPosNew[[1]] >= obs[[1, 1]] && newPosNew[[1]] <= obs[[2, 1]] && newPosNew[[2]] >= obs[[1, 2]] && newPosNew[[2]] <= obs[[2, 2]] ) || (newPosNewPos[[1]] >= obs[[1, 1]] && newPosNewPos[[1]] <= obs[[2, 1]] && newPosNewPos[[2]] >= obs[[1, 2]] && newPosNewPos[[2]] <= obs[[2, 2]]), reflect = True; If[ Abs[newPos[[1]] - obs[[1, 1]]] <= particleRadius || Abs[newPos[[1]] - obs[[2, 1]]] <= particleRadius, xCollision = True ]; If[ Abs[newPos[[2]] - obs[[1, 2]]] <= particleRadius || Abs[newPos[[2]] - obs[[2, 2]]] <= particleRadius, yCollision = True ]; If[xCollision, newVel[[1]] = -vel[[1]]]; If[yCollision, newVel[[2]] = -vel[[2]]]; ], {obs, obstacles} ]; If[reflect, newPos = pos - vel*timeStep]; If[reflect, newPos += newVel*minTimeStep]; {newPos, newVel} ]; updateGraph[positions_, velocities_] := Transpose[ MapThread[ reflectBounceParticleWall, { positions + velocities*timeStep, velocities, ConstantArray[obstacles, Length[positions]] } ] ]; onCollideHandle[positions_, velocities_] := Module[ {newVelocities = velocities, angle, v1, v2, speed1, speed2}, Do[ If[i != j && Norm[positions[[i]] - positions[[j]]] < 2*particleRadius, angle = RandomReal[{0, 2 Pi}]; speed1 = Norm[velocities[[i]]]; speed2 = Norm[velocities[[j]]]; v1 = speed1*{Cos[angle], Sin[angle]}; v2 = speed2*{Cos[angle + Pi], Sin[angle + Pi]}; newVelocities[[i]] = v2; newVelocities[[j]] = v1; ], {i, ballCount}, {j, i + 1, ballCount}]; newVelocities ]; stringRewritePath[positions_, paths_] := MapThread[Append, {paths, positions}]; findFirstWinFirstTime[positions_, yThreshold_] := Module[ {foundPosition = None}, Do[ If[positions[[i, 2]] <= yThreshold, foundPosition = i; Break[];], {i, Length[positions]}]; foundPosition ]; winFirstTime = None; positionSeries = Table[ paths = stringRewritePath[positions, paths]; If[winFirstTime === None, With[ {win = findFirstWinFirstTime[positions, 1.5]}, If[win =!= None, winFirstTime = win] ] ]; velocities = onCollideHandle[positions, velocities]; {positions, velocities} = updateGraph[positions, velocities]; {positions, velocities, paths}, {t, 0, 10, timeStep} ]; highlightPath[paths_, index_] := If[ index =!= None && index <= Length[paths], {Thick, Purple, Line[paths[[index]]]}, {} ]; pizzatoppings = ListAnimate[ Table[ Graphics[ { highlightPath[paths, winFirstTime], Table[ {colors[[i]], PointSize[Large], Point[positionSeries[[frame, 1, i]]]}, {i, ballCount} ], Black, Rectangle[#1, #2] & @@@ obstacles }, PlotRange -> {{0, dims[[1]] + 1}, {0, dims[[2]] + 1}}, Frame -> True ], {frame, Length[positionSeries]}], AnimationRate -> 10 ]; pizzatoppings Does everybody who gets the flu, is there a higher probability of them getting this other thing later? The question of Brownian motion becomes a playground for testing theories of emergent properties like the trajectory of the paths of particles as an allegory for the process of discovery itself, whether homomorphic encryption on zero-knowledge, mathematically simplistic things can be understood. How can we understand the context of the behavior of the system of Brownian Motion Maze Solving which is the best maze solving..if you were wondering how the behavior of a system can be understood in the context of the observer's interaction with the system, the observer which witnesses and tracks the particles' movements, the observer (simulation) must have rules or assumptions that govern its interaction with the system (particles in the maze). And I do, I end up using what particle dynamics have already figured out about the step-back mechanism for determining the microscopic interparticle interactions..from how goto can be turned into an if statement to the philosophical implications of observer-dependent realities. Export["pizzatoppings.mov", pizzatoppings]  "pizzatoppings.mov" Choose the coordinates describing the foundations of the Lines...the way you form the uniform distributions, these are some descriptive lines! What did we get from the futuristic foundation of the cellular automaton based on And..no, we can't get anything from the cellular automaton. This is so creative, watch the balls diverge at the beginning. Here's something we can do: focus on having the desire to decide to run the simulation so many times until the end motion catches up to the end-difficulty..that's 2000 balls but no walls!? When y'all tie all the vectors together and graph this Brownian Motion, it looks like maze-solving doesn't it. g = GridGraph[{8, 12}]; spanningTree = FindSpanningTree[ NeighborhoodGraph[g, RandomSample[VertexList[g], 8*12], 1]] ListPlot[ Flatten[ Table[Transpose@ RandomFunction[WienerProcess[\[Mu], \[Sigma]], {0, 1, .001}, 2][ "States"], {\[Mu], .001, 1, .1}, {\[Sigma], .001, 1, .1}]], PlotTheme -> "Detailed", PlotRange -> Full, ColorFunction -> "Rainbow", ImageSize -> 300] Have you seen the other, the new Brownian Motion Simulator WienerProcess? It's so dynamic it's disgusting. I always wondered how you drew the EEG signal of a cat, a nematode, like that, and how you do the Dynamic content. The color resembles burnt coffee, it's a new world thing. I guess that, I should thank Donavon for being such a pal and for being my ghost philosopher, James for the Brownian Motion Graph, and Varun for the Demonstrations Projects. I asked him and he said...these successor balls just keep coming in and updating, wouldn't it be nice if we could map them all out? dims = {3, 5}; hallwayThickness = 0.8; ballCount = 100; initPs = {1 + hallwayThickness/2, dims[[1]] + hallwayThickness/2}; g = GridGraph[dims]; spanningTree = FindSpanningTree[GridGraph[dims, EdgeWeight -> {_ :> RandomReal[]}]]; wallsRegion = RegionDifference[ #, Rectangle[{dims[[2]], hallwayThickness}, {dims[[2]], 0} + {hallwayThickness, 1}]] &@ RegionDifference[ Rectangle[{1, 1} - 1 + hallwayThickness, Reverse[dims] + 1], RegionDilation[ DiscretizeGraphics[ Line[GraphEmbedding[spanningTree][[#]]] & /@ List @@@ EdgeList[spanningTree]], Rectangle[{0, 0}, {1, 1}*hallwayThickness]]]; positionSeries = Reap[ Sow[ps = ConstantArray[initPs, ballCount]]; While[ And @@ RegionMember[ Rectangle[{1, 1} - 1 + hallwayThickness, Reverse[dims] + 1]][ ps], vs = RandomPoint[Circle[], ballCount]*0.1; ps += vs; ps -= vs*Boole[RegionMember[wallsRegion][ps]]; Sow[ps]]][[2, 1]]; winningIndex = FirstPosition[ RegionMember[ Rectangle[{1, 1} - 1 + hallwayThickness, Reverse[dims] + 1]]@ Last@positionSeries, False][[1]]; ballDistanceRanking = Ordering[ Max /@ Total[(Threaded[initPs] - Transpose[positionSeries])^2, {3}]]; distanceFromStartGrid = Function[positions, EuclideanDistance[initPs, #] & /@ positions]; distanceFromEndGrid = Function[positions, EuclideanDistance[Reverse[dims] + 1, #] & /@ positions]; plotScatterPlot = Function[{i, distances}, ListPlot[{Transpose[{Range[Length[distances]], distances}], {{winningIndex, distances[[winningIndex]]}}}, PlotStyle -> {Automatic, Directive[Red, PointSize[Large]], Directive[Blue, PointSize[Large]]}, PlotTheme -> "Detailed", PlotRange -> All, ColorFunction -> "Rainbow", Frame -> True, FrameLabel -> {"i", "Distance Euclidean"}, LabelStyle -> {White, 12}, Background -> White, ImageSize -> 300]]; Manipulate[ Row[{Graphics[{Black, Opacity[0.5], wallsRegion, {Magenta, Thick, Circle[positionSeries[[i, winningIndex]], 0.2], Thick, Line[positionSeries[[;; i, winningIndex]], VertexColors -> (ColorData["Rainbow"] /@ Rescale[Range[i]])]}, {Yellow, Thick, Circle[positionSeries[[i, vertexIndexed]], 0.2], Thin, Line[positionSeries[[All, vertexIndexed]]]}, Green, Opacity[1], PointSize[Medium], Point[positionSeries[[i]]], Magenta, Opacity[1], Line[positionSeries[[All, ballDistanceRanking[[pathSelect]]]]], Yellow, Line[positionSeries[[All, vertexIndexed]]] }, ImageSize -> 300, Background -> White], plotScatterPlot[i, distanceFromStartGrid[positionSeries[[i]]]], plotScatterPlot[i, distanceFromEndGrid[positionSeries[[i]]]]}], {i, 1, Length[positionSeries], 1, Appearance -> "Open", AnimationRate -> 10}, {vertexIndexed, 1, ballCount, 1, Appearance -> "Open"}, {pathSelect, 1, ballCount, 1, Appearance -> "Open"}] This is a beautiful topic and I don't know how else to put it. I guess that I really shouldn't have used the resource for vector art, the spanningTree. I did a flip flop, put the old maze back and now we can more clearly delineate the Boolean of wall membership, when you lump it by itself..lump? No, no. Sow the position parts? Sow the position parts. Show how we can get the positionSeries for instance to show the path for one particle field, set some directions for future research. It would be so cool to put some magnetic fields or maybe wind. What would be the meaning of that? Ya know, how philosophy symbolically reduces to explain the nature of everything. And in this retro simulation we've got a can-full of worms, spider-like paths, in pseudo-random velocity, in a maze. What would you do, if you wanted to in form form the passages and walls and had a FindSpanningTree and GridGraph? I wonder why maybe because we haven't done experiments on Brownian Motion or not? Because we don't know? Dohh, I don't know. I used to traverse your simulation, last time and actually this is even more fun I think I escaped the big maze and now we've got a new maze. Maze traversal just wouldn't be the same without you. What is this, a simulation for ants? It's a watercolor made for the ants. That's the extent of, the particles go from the place they're transmitted to the place they're received, which may or may not be the place at which the grid starts and stops. https://reference.wolfram.com/language/example/BrownianMotion.htmlhttps://demonstrations.wolfram.com/BrownianMotionPathAndMaximumDrawdown/https://demonstrations.wolfram.com/ExitTimesOfBrownianMotionIn3D/https://demonstrations.wolfram.com/BrownianMotionIn2DAndTheFokkerPlanckEquation/https://demonstrations.wolfram.com/TwoDimensionalFractionalBrownianMotion/
Posted 2 years ago
 -- you have earned Featured Contributor Badge Your exceptional post has been selected for our editorial column Staff Picks http://wolfr.am/StaffPicks and Your Profile is now distinguished by a Featured Contributor Badge and is displayed on the Featured Contributor Board. Thank you!
Community posts can be styled and formatted using the Markdown syntax.