|
| 12 Jul 2013 10:31 AM |
Its rather simple, assume you have a grid of 5x7, and a player starts from the bottom, working their way up to the top.
Finish O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O Start
A player can move horizontal, vertical and diagonal.
O O O O P O O O O
Can someone tell if there is an algorithm which would create a random path which can't intersect with itself (spaced out so that the player can't skip points) example.
Finish X O O O O O X O O O O O X X O O O O O X O O X O X O X O X O O X O O O Start
- QuadFactor |
|
|
| Report Abuse |
|
|
smurf279
|
  |
| Joined: 15 Mar 2010 |
| Total Posts: 6871 |
|
| |
|
1waffle1
|
  |
| Joined: 16 Oct 2007 |
| Total Posts: 16381 |
|
|
| 12 Jul 2013 10:36 AM |
Each open cell has two open neighbors but the first and the last Possible directions the line can move in is determined by which neighboring closed cells do not already have a second open neighbor. If the neighboring cell happens to be a border then don't go backwards until the line isn't at the border anymore. |
|
|
| Report Abuse |
|
|
|
| 12 Jul 2013 10:37 AM |
Come to think of it, I guess it is a maze.
- QuadFactor |
|
|
| Report Abuse |
|
|
1waffle1
|
  |
| Joined: 16 Oct 2007 |
| Total Posts: 16381 |
|
|
| 12 Jul 2013 10:40 AM |
| It isn't a maze, it's a squiggly line. |
|
|
| Report Abuse |
|
|
blocco
|
  |
| Joined: 14 Aug 2008 |
| Total Posts: 29474 |
|
| |
|
smurf279
|
  |
| Joined: 15 Mar 2010 |
| Total Posts: 6871 |
|
|
| 12 Jul 2013 10:43 AM |
| what waffle said doesn't really make sense. . . anyways just search up recursive backtracking maze |
|
|
| Report Abuse |
|
|
blocco
|
  |
| Joined: 14 Aug 2008 |
| Total Posts: 29474 |
|
|
| 12 Jul 2013 10:43 AM |
it made perfect sense it's not a maze, it's a squiggly line |
|
|
| Report Abuse |
|
|
smurf279
|
  |
| Joined: 15 Mar 2010 |
| Total Posts: 6871 |
|
| |
|
1waffle1
|
  |
| Joined: 16 Oct 2007 |
| Total Posts: 16381 |
|
|
| 12 Jul 2013 12:25 PM |
| No, you're just incompetent. |
|
|
| Report Abuse |
|
|
|
| 12 Jul 2013 12:37 PM |
1.Make a straight line as the path 2.Pick a point on the path. Move attempt to move it to a random direction by one unit. Add more path points to keep the path intact if necessary. OXO//original OXO OXO
OXO//Move middle one unit OOX OXO
OXOO//Move it again yay OOOX OXOO
OXXO//add points to keep path intact. Try to find configuration which works. OOOX OXXO
If any of those steps fails (eg. moving causes path to become invalid, or you cant place the points required to keep path connected) dont do the movement. 3.goto 2. |
|
|
| Report Abuse |
|
|
woot3
|
  |
| Joined: 10 Nov 2008 |
| Total Posts: 3599 |
|
|
| 12 Jul 2013 01:56 PM |
You'll always have an entrance point, left with 3 other directions. Starting at point N check to see which of the 3 are available then use this rule.
#1 If there are squares open, select randomly and move onto that sqaure. #2 If no squares are open move back and mark that square invalid.
It's just trial and error, however I imagine sometimes it will error so you may also want to add a 3rd rule.
#3 If the square is closer to the goal, use it. |
|
|
| Report Abuse |
|
|
AdvRobot
|
  |
| Joined: 09 Aug 2012 |
| Total Posts: 172 |
|
|
| 12 Jul 2013 01:58 PM |
| One of projects I plan on doing is this! I never knew someone else would be working on this too. |
|
|
| Report Abuse |
|
|
smurf279
|
  |
| Joined: 15 Mar 2010 |
| Total Posts: 6871 |
|
|
| 12 Jul 2013 02:18 PM |
"No, you're just incompetent."
another word for dumb donkey |
|
|
| Report Abuse |
|
|
|
| 12 Jul 2013 03:33 PM |
| This would be a lot simpler if the line couldnt go back towards the beginning. |
|
|
| Report Abuse |
|
|
woot3
|
  |
| Joined: 10 Nov 2008 |
| Total Posts: 3599 |
|
|
| 12 Jul 2013 04:26 PM |
| Radio, that's why you should check for the closest point to the goal. |
|
|
| Report Abuse |
|
|
1waffle1
|
  |
| Joined: 16 Oct 2007 |
| Total Posts: 16381 |
|
|
| 12 Jul 2013 04:27 PM |
| Make a straight line and then bend it in random places until it isn't allowed to change anymore. |
|
|
| Report Abuse |
|
|
woot3
|
  |
| Joined: 10 Nov 2008 |
| Total Posts: 3599 |
|
|
| 12 Jul 2013 04:29 PM |
| Make it so it can't get closer to the start unless it has to, then let it go in random squiggly directions :D |
|
|
| Report Abuse |
|
|
|
| 13 Jul 2013 05:11 AM |
@woot
but i think he wants it to go back towards the goal ._. |
|
|
| Report Abuse |
|
|
|
| 13 Jul 2013 12:43 PM |
Here. I just made this code and tested it. Enjoy.
local NodesPerStep = 20 -- should be lag-less
local function GetID(Node) return Node.X .. " - " .. Node.Y end
local function GetChildren(Node, ClosedNodes, AvailableNodes) local x, y = Node.X, Node.Y local allChildren = { Vector2.new(x-1,y-1); Vector2.new(x-1,y); Vector2.new(x-1,y+1); Vector2.new(x,y-1); -- Vector2.new(x,y); -- Skip self Vector2.new(x,y+1); Vector2.new(x+1,y-1); Vector2.new(x+1,y); } local availChildren = {} for _, child in pairs(allChildren) do local id = GetID(child) if not ClosedNodes[id] and AvailableNodes[id] then availChildren[#availChildren+1] = child end end return availChildren end
local function GetRandomPath(StartNode, FinishNode, AvailableNodes) local Path = {} local ClosedNodes = {} local FinishID = GetID(FinishNode)
if not AvailableNodes[FinishID] then return "The Finish Node is not on the map!" end local CurrentNode = StartNode while wait() do for i = 1, NodesPerStep do print("Ran iteration", CurrentNode.X, CurrentNode.Y) if GetID(CurrentNode) == FinishID then return Path end local children = GetChildren(CurrentNode, ClosedNodes, AvailableNodes) if #children == 0 then if #Path > 1 then CurrentNode = Path[#Path-1] Path[#Path] = nil else return "No Possible Path!" end else CurrentNode = children[math.random(1, #children)] Path[#Path+1] = CurrentNode ClosedNodes[GetID(CurrentNode)] = true end end end end
local function SetupMap(size, position) local xBase = position.X local yBase = position.Y local n = 0 local Map = {} for x = 1, size.X do for y = 1, size.Y do n = n + 1 Map[(xBase+x) .. " - " .. (yBase+y)] = true if n % NodesPerStep == 0 then wait() end end end return Map end
--Now, lets run the code: local map = SetupMap( Vector2.new(5,7), Vector2.new(0,0) ) local path = GetRandomPath( Vector2.new(2,0), Vector2.new(2,6), map ) if type(path) == "string" then print(path) else for _, node in pairs(path) do print(node.X, node.Y) end end
|
|
|
| Report Abuse |
|
|
|
| 13 Jul 2013 12:50 PM |
My code above makes a "map" of all possible positions, then it sets a start and finish. it then goes into a loop starting with the start position, and finds all nodes next to it that are open, and haven't been traveled before, and selects a random one to move to next. if there is no open nodes, then it moves back a node, and tries again. If it next node is the finish node it return that it finished.
If the finished node isn't on the map, then it can't be reachable and returns a string. If you make a custom map. And make a island that finish is on then it will run and eventually figure out that it is impossible to reach finish and send a string back.
It returns a string, or a table of vector2 positions from the start position (excluding the start position) to the finish position (including the finish position).
This uses all adjacent nodes, including diagonal nodes. |
|
|
| Report Abuse |
|
|
|
| 13 Jul 2013 12:58 PM |
| btw, I used the similar A* algorithm in 3D to make my pathfinder available in ArbiterOfDeath's free models. |
|
|
| Report Abuse |
|
|