generic image
Processing...
  • Games
  • Catalog
  • Develop
  • Robux
  • Search in Players
  • Search in Games
  • Search in Catalog
  • Search in Groups
  • Search in Library
  • Log In
  • Sign Up
  • Games
  • Catalog
  • Develop
  • Robux
   
ROBLOX Forum » Game Creation and Development » Scripters
Home Search
 

Re: Is there a similar algorithm to create this?

Previous Thread :: Next Thread 
QuadFactor is not online. QuadFactor
Joined: 19 Apr 2011
Total Posts: 333
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 is not online. smurf279
Joined: 15 Mar 2010
Total Posts: 6871
12 Jul 2013 10:34 AM
like a perfect maze?
Report Abuse
1waffle1 is not online. 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
QuadFactor is not online. QuadFactor
Joined: 19 Apr 2011
Total Posts: 333
12 Jul 2013 10:37 AM
Come to think of it, I guess it is a maze.

- QuadFactor
Report Abuse
1waffle1 is not online. 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 is not online. blocco
Joined: 14 Aug 2008
Total Posts: 29474
12 Jul 2013 10:40 AM
^
Report Abuse
smurf279 is not online. 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 is not online. 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 is not online. smurf279
Joined: 15 Mar 2010
Total Posts: 6871
12 Jul 2013 10:44 AM
before that
Report Abuse
1waffle1 is not online. 1waffle1
Joined: 16 Oct 2007
Total Posts: 16381
12 Jul 2013 12:25 PM
No, you're just incompetent.
Report Abuse
Radioaktiivinen is not online. Radioaktiivinen
Joined: 25 Apr 2009
Total Posts: 18629
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 is not online. 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 is not online. 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 is not online. 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
Radioaktiivinen is not online. Radioaktiivinen
Joined: 25 Apr 2009
Total Posts: 18629
12 Jul 2013 03:33 PM
This would be a lot simpler if the line couldnt go back towards the beginning.
Report Abuse
woot3 is not online. 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 is not online. 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 is not online. 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
Radioaktiivinen is not online. Radioaktiivinen
Joined: 25 Apr 2009
Total Posts: 18629
13 Jul 2013 05:11 AM
@woot

but i think he wants it to go back towards the goal ._.
Report Abuse
darknightofVorhan is not online. darknightofVorhan
Joined: 23 Jun 2008
Total Posts: 667
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
darknightofVorhan is not online. darknightofVorhan
Joined: 23 Jun 2008
Total Posts: 667
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
darknightofVorhan is not online. darknightofVorhan
Joined: 23 Jun 2008
Total Posts: 667
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
Previous Thread :: Next Thread 
Page 1 of 1
 
 
ROBLOX Forum » Game Creation and Development » Scripters
   
 
   
  • About Us
  • Jobs
  • Blog
  • Parents
  • Help
  • Terms
  • Privacy

©2017 Roblox Corporation. Roblox, the Roblox logo, Robux, Bloxy, and Powering Imagination are among our registered and unregistered trademarks in the U.S. and other countries.



Progress
Starting Roblox...
Connecting to Players...
R R

Roblox is now loading. Get ready to play!

R R

You're moments away from getting into the game!

Click here for help

Check Remember my choice and click Launch Application in the dialog box above to join games faster in the future!

Gameplay sponsored by:
Loading 0% - Starting game...
Get more with Builders Club! Join Builders Club
Choose Your Avatar
I have an account
generic image