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: A* / Datastructure Help

Previous Thread :: Next Thread 
Quenty is not online. Quenty
Joined: 03 Sep 2009
Total Posts: 9316
24 May 2012 07:40 PM
What does it appear that I am doing wrong? My datastructures are kind of random, and I need advice.

This is an A* pathfinder. I've worked on it for about 8 hours, so I kind of think... you know, I should ask here.

I'm following the procedure from Amit's A* stuff. which is here:

------------------------------------------------------
OPEN = priority queue containing START
CLOSED = empty set
while lowest rank in OPEN is not the GOAL:
current = remove lowest rank item from OPEN
add current to CLOSED
for neighbors of current:
cost = g(current) + movementcost(current, neighbor)
if neighbor in OPEN and cost less than g(neighbor):
remove neighbor from OPEN, because new path is better
if neighbor in CLOSED and cost less than g(neighbor): **
remove neighbor from CLOSED
if neighbor not in OPEN and neighbor not in CLOSED:
set g(neighbor) to cost
add neighbor to OPEN
set priority queue rank to g(neighbor) + h(neighbor)
set neighbor's parent to current

reconstruct reverse path from goal to start
by following parent pointers
------------------------------------------------------
Here is my map generating function: Captures stuff from terrain.

function GenerateMap(TerrainY) -- TerrainY is the height to scan it for. Scanning, not really generating.
if not _G.Map then
print("Generating Map")
local TimeTook = tick()
for X=LowerX, UpperX do
Map[X] = {}
local Ref = Map[X]
for Y=LowerY, UpperY do
local Material--[[, Type, Orientation--]] = TerrainGetCell(Terrain, X,TerrainY,Y)
Ref[Y] = {}
Ref[Y].Transversable = (Material == Enum.CellMaterial.Empty) --Trans --Empty or not. :D
Ref[Y].Neighbors = {
{X = X+1; Y = Y+1};
{X = X; Y = Y+1};
{X = X-1; Y = Y+1};
{X = X-1; Y = Y};
{X = X+1; Y = Y};
{X = X-1; Y = Y-1};
{X = X; Y = Y-1};
{X = X+1; Y = Y-1};
}
end
if X % 10 == 0 then --Don't lag out the server at the beginning...
print("Wait For "..X)
wait()
end
end
_G.Map = Map
print("It took: "..tick()-TimeTook.." seconds to complete the terrain capture")
else
print("Map has already been generated, getting it from _G.Map")
Map = _G.Map
end
end





Actual Code:
------------------------------------------------------
If you're an A* person, can you just kind of look over this, and tell me if anything looks wrong... I mean, This is annoying. It goes towards the target, get's all these 'Red' bricks, which aren't suppose to happen (Errors), and then it somehow runs out of items in the open set...

Anyway, I know there's a logical problem here. SOMEONE FIND IT pl0x?

All, I really really need advice on datastructures.


local function AStar(Start, Goal)
print("AStar start")

Start["GScore"] = 0 -- Distance from start.
Start["HScore"] = Heuristic(Start,Goal) -- Estimated Distance from Goal
Start["FScore"] = Start.GScore + Start.HScore -- The Final Score

local OpenSet = {Start} -- The OpenSet is the set of nodes that need to be check. In each repetition, it pulls out the smallest 'Scoring' one, and checks it.
local ClosedSet = {} -- The ClosedSet is the set of nodes that have already been visited


local Continue = true -- Until the Goal is found, continue will be true.
local LowestNode, IndexVal
local Reps = 0

local function GetLowestRankInOpen()
local LowestNode, IndexVal;
local CurrentNodeFScore = math.huge
print("OpenSet has :"..#OpenSet.." options")
for Index, Node in pairs(OpenSet) do
if Node.FScore <= CurrentNodeFScore then
CurrentNodeFScore = Node.FScore
LowestNode = Node
IndexVal = Index;
end
end
return LowestNode, IndexVal;
end

local function NodeIsTransversable(NodeX, NodeY)
local MapX = Map[NodeX] -- Node out of bounds?
if not MapX then
print("Node out of bounds")
return false
end
local MapXY = MapX[NodeY] -- Node out of bounds?
if not MapXY then
print("Node out of bounds")
return false
end
return MapXY.Transversable
end

function NodeIsInOpenSet(NodeX, NodeY)
for Index, Node in pairs(OpenSet) do
if Node.X == NodeX and Node.Y == NodeY then
return true, Node, Index
end
end
return false
end

function NodeIsInClosedSet(NodeX, NodeY)
for Index, Node in pairs(ClosedSet) do
if Node.X == NodeX and Node.Y == NodeY then
return true, Node, Index
end
end
return false
end

local function ReconstructPath(Node, Tab)
Tab = Tab or {}
table.insert(Tab, Node)
return Node.Source and ReconstructPath(Node.Source, Tab) or Tab;
end

local function Check(Num)
for _, Node in pairs(OpenSet) do
if Node.FScore < Num then
print("failed @ "..Node.FScore)
end
end
end

while #OpenSet > 0 do
Reps = Reps + 1
print("Loop #: "..Reps)
LowestNode, IndexVal = GetLowestRankInOpen()
print(LowestNode and "Lowest node is there" or "Lowest node is not there")
local LowestNodeX = LowestNode.X
local LowestNodeY = LowestNode.Y
print("FScore: "..LowestNode.FScore)
Check(LowestNode.FScore)
wait(0.1)
if (LowestNodeX ~= Goal.X) and (LowestNodeY ~= Goal.Y) then
ClosedSet[#ClosedSet+1] = LowestNode
OpenSet[IndexVal] = nil

if OpenSet[IndexVal] then
print("Hack")
end

RenderNiceBrick(LowestNodeX, LowestNodeY, BrickColor.new("Mid gray"))

for _, NeighborNode in pairs(Map[LowestNodeX][LowestNodeY].Neighbors) do
local NeighborNodeX = NeighborNode.X -- Speed things up
local NeighborNodeY = NeighborNode.Y
if NodeIsTransversable(NeighborNodeX, NeighborNodeY) then
local NeighborGScore = LowestNode.GScore + Heuristic(LowestNode, NeighborNode)
local NeighborHScore = Heuristic(NeighborNode, Goal)
local NeighborFScore = NeighborHScore + NeighborGScore
local NodeIsInOpen, OpenNode, OpenIndex = NodeIsInOpenSet(NeighborNodeX, NeighborNodeY)
local NodeIsInClosed, ClosedNode, ClosedIndex = NodeIsInClosedSet(NeighborNodeX, NeighborNodeY)

print("Node["..NeighborNodeX.."]["..NeighborNodeY.."]")
print("   Node is in Open: ",NodeIsInOpen)
print("   Node is in Closed: ",NodeIsInClosed)
print("   Node FScore: ", NeighborFScore)

if NodeIsInOpen and NeighborGScore < OpenNode.GScore then
RenderNiceBrick(NeighborNodeX,NeighborNodeY, BrickColor.new("Bright orange"))
--print("   Old position is better")
OpenSet[OpenIndex] = nil
--NodeIsInOpen = false
end

if NodeIsInClosed and NeighborHScore < ClosedNode.GScore then
RenderNiceBrick(NeighborNodeX,NeighborNodeY, BrickColor.new("Bright red"))
print("   Heuristic Error")
ClosedSet[ClosedIndex] = nil
NodeIsInClosed = false
end

if not NodeIsInClosed and not NodeIsInOpen then
print("   Node identified")
RenderNiceBrick(NeighborNodeX,NeighborNodeY, BrickColor.new("Bright blue"))
local NewNode = {}
NewNode.X = NeighborNodeX
NewNode.Y = NeighborNodeY
NewNode["GScore"] = NeighborGScore
NewNode["HScore"] = NeighborHScore
NewNode["FScore"] = NeighborFScore
NewNode.Source = LowestNode
OpenSet[#OpenSet+1] = NewNode
end
else
RenderNiceBrick(NeighborNodeX,NeighborNodeY, BrickColor.new("Hot pink"))
print("Can't walk on dat")
end
end
else
RenderNiceBrick(LowestNode.X,LowestNode.Y, BrickColor.new("Bright yellow"))
Continue = false
print("Found goal")
end
end

print("Done with A*")
return true, ReconstructPath(LowestNode, {});
end
Report Abuse
Tenal is not online. Tenal
Joined: 15 May 2011
Total Posts: 18684
24 May 2012 07:42 PM
idk
Report Abuse
Quenty is not online. Quenty
Joined: 03 Sep 2009
Total Posts: 9316
24 May 2012 07:45 PM
:(

*Facepalm*
Report Abuse
Quenty is not online. Quenty
Joined: 03 Sep 2009
Total Posts: 9316
24 May 2012 07:46 PM
I should go use the inefficient version I had...

I should make Julien mad.

Ololol.

Nah. Someone please please help. D:
Report Abuse
Aerideyn is not online. Aerideyn
Joined: 16 Jan 2010
Total Posts: 1882
24 May 2012 08:13 PM
It has been too long.. i remember i managed to get one working about 6 months ago.. i probably have the script around here somewhere though from memory it worked on a 1stud voxel grid (floor the position of the player for start node etc) and didnt support multiple levels.. but if you want it i can probably upload the script.

Report Abuse
Quenty is not online. Quenty
Joined: 03 Sep 2009
Total Posts: 9316
24 May 2012 08:48 PM
I have a working version.

I want to know what's wrong with this one I wrote now...

See any design flaws?
Report Abuse
ENET is not online. ENET
Joined: 01 Jan 2010
Total Posts: 4820
24 May 2012 10:32 PM
ugly code is ugly.
Report Abuse
MajorTyco is not online. MajorTyco
Joined: 09 Apr 2010
Total Posts: 1989
24 May 2012 10:45 PM
I agree. That code makes me..*hesitate, pose like that guy in the fiberOne commerical* sad.

Error in function Gag, line 1337: Too Lazy to Write Variable "siggy"
Report Abuse
NXTBoy is not online. NXTBoy
Joined: 25 Aug 2008
Total Posts: 4533
25 May 2012 03:26 AM
For a start, I'd be tempted to use the nodes as keys rather than values in open and closed set. Possibly something like this:

    openset[node] = {
        g = ...,
        h = ...,
        f = ...,
        cameFrom = anotherNode -- used to build up the path backwards
    }

This is better than attaching properties to the nodes themselves, because you can reuse the nodes when you run the algorithm again.
Report Abuse
NXTBoy is not online. NXTBoy
Joined: 25 Aug 2008
Total Posts: 4533
25 May 2012 03:57 AM
Also, a quick code style note - it's bad practice to use tabs for alignment (equals signs, comments, etc), since they only align if the tab size is the same as the one you were using. Tabs for indentation, spaces for alignment.
Report Abuse
Quenty is not online. Quenty
Joined: 03 Sep 2009
Total Posts: 9316
25 May 2012 02:07 PM
I tried to use Nodes as keys, but that means I had to use to do some really hacky stuff or something..


As for alignment... Yeah, good idea.
Report Abuse
trappingnoobs is not online. trappingnoobs
Joined: 05 Oct 2008
Total Posts: 19100
25 May 2012 03:32 PM
this might be wrong but surely it's a bit of a stupid idea to cram hundreds of functions into a function

it'd need to redo them into the memory every time it ran and since it's garbage collected not manual and it obviously isn't nice on the processor to keep defining functions over and over, you should just put them in a table or something if you're going to be using them often
Report Abuse
Quenty is not online. Quenty
Joined: 03 Sep 2009
Total Posts: 9316
25 May 2012 03:35 PM
Hmm.. yeh.

I know I have a really big logical problem in that mess.... Like a REALLY big one. I just can't find it.

But yes. Tell me all my bad scripting practices... I know I have a lot of them.
Report Abuse
NXTBoy is not online. NXTBoy
Joined: 25 Aug 2008
Total Posts: 4533
25 May 2012 03:37 PM
They have closures on the surrounding variables - that's why they have to be there. The only solution would be object-orientation and metatables, which would probably be overkill.

Constructing a handful of functions costs nothing compared to running an A* algorithm.
Report Abuse
Quenty is not online. Quenty
Joined: 03 Sep 2009
Total Posts: 9316
25 May 2012 03:45 PM
@NXTBoy... No. Easy solution:

function Whatever(ATable, restOfarguments)
-- Do the stuff...
end

Report Abuse
NXTBoy is not online. NXTBoy
Joined: 25 Aug 2008
Total Posts: 4533
25 May 2012 03:49 PM
Bleh. Looks messy. I prefer your closure way of doing things.
Report Abuse
Quenty is not online. Quenty
Joined: 03 Sep 2009
Total Posts: 9316
26 May 2012 10:17 AM
True. True.

Still, any way works fine. Environments are tricky.
Report Abuse
2013henry is not online. 2013henry
Joined: 09 Apr 2013
Total Posts: 39768
13 Apr 2016 12:39 AM
What...?
Report Abuse
Flux_Capacitor is not online. Flux_Capacitor
Joined: 07 Apr 2008
Total Posts: 45720
13 Apr 2016 12:42 AM
2013henry you're stupid.
You bumped a 4 year old thread in case you didn't know.
Report Abuse
arshiaslaya is not online. arshiaslaya
Joined: 04 Nov 2012
Total Posts: 2670
13 Apr 2016 01:48 AM
Kappa


Report Abuse
arshiaslaya is not online. arshiaslaya
Joined: 04 Nov 2012
Total Posts: 2670
13 Apr 2016 02:52 PM
Daily bump


Report Abuse
Exgle is not online. Exgle
Joined: 03 Jun 2011
Total Posts: 132
14 Apr 2016 10:52 AM
My brain
Report Abuse
arshiaslaya is not online. arshiaslaya
Joined: 04 Nov 2012
Total Posts: 2670
14 Apr 2016 04:50 PM
Bump


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