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: Implementing a Binary Heep

Previous Thread :: Next Thread 
Quenty is not online. Quenty
Joined: 03 Sep 2009
Total Posts: 9316
24 May 2012 02:47 PM
I have an A* thing, and I want to store data in a binary heap.

Right now it's stored in an indexed table, like..

OpenSet[1] = { X, Y, Source, GScore, HScore, et cetera, et cetera...

Just a table with another table of information....

How would I use a binary heap, and would it be that much faster? Here's the code I use to create the map from terrain:

function GenerateMap(TerrainY) -- TerrainY is the height to scan it for. Scanning, not really generating.
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
print("It took: "..tick()-TimeTook.." seconds to complete the terrain capture")
end

The point of this is to try to pre-calculate as much as I can, without lagging the server.

If I made a binary heap, how would it work? I mean, I'm indexing it by [X][Y] values, so...

Report Abuse
Sorcus is not online. Sorcus
Forum Moderator
Joined: 29 Nov 2010
Total Posts: 3775
24 May 2012 04:01 PM
Stravant has some data collected which proves that an array works just as well as a binary heap for A* in ROBLOX. Ping him.

~Sorcus
Report Abuse
lah30303 is not online. lah30303
Joined: 15 Feb 2008
Total Posts: 10027
24 May 2012 04:10 PM
I have done binary heaps before, but it wasn't very well written and it was 2 years ago so I don't remember it well. If you want to you can look at what I did in this model:

http://www.roblox.com/A-Pathfinder-with-binary-heaps-V-1A-item?id=22333228
Report Abuse
sncplay42 is not online. sncplay42
Joined: 27 Nov 2008
Total Posts: 11891
24 May 2012 04:12 PM
"Stravant has some data collected which proves that an array works just as well as a binary heap for A*"

I know you can store a binary heap in an array (see the wikipedia article on them)...
Report Abuse
sncplay42 is not online. sncplay42
Joined: 27 Nov 2008
Total Posts: 11891
24 May 2012 04:13 PM
And for the record that's what I use in my AI system.
Report Abuse
Sorcus is not online. Sorcus
Forum Moderator
Joined: 29 Nov 2010
Total Posts: 3775
24 May 2012 04:13 PM
I wasn't saying that he implementing a binary heap in an arry >> I was saying a regular array performs just as well.

~Sorcus
Report Abuse
Quenty is not online. Quenty
Joined: 03 Sep 2009
Total Posts: 9316
24 May 2012 05:00 PM
Hmm... thanks.

I seem to be having trouble implimenting my A* in a way that it's efficient with the indexing stuffz.

I'm having indecision on how to store information...
Uggg...
Report Abuse
Quenty is not online. Quenty
Joined: 03 Sep 2009
Total Posts: 9316
24 May 2012 05:08 PM
I think that using a metatable to find if an index exists is getting just a bit confusing....

Uggg...

This is what I've tried...

- Using the 'Table' of the node itself as an index.
However, this meant I had to either use some fancy metatable hack, or copy a table of 100,000 or so values every call...

- Using tables with [X][Y] indexs...

I'm trying the tables thing again...

I'm pretty sure I don't want to talk about the other thing's I've tried.
Report Abuse
MajorTyco is not online. MajorTyco
Joined: 09 Apr 2010
Total Posts: 1989
24 May 2012 05:15 PM
Inferring from the article on Wikipedia about binary heaps, it seems that it would be much easier and more efficient, or at least just as efficient, to just use an array- as Sorcus posted.

"I remain just one thing, and one thing only — and that is a clown. It places me on a far higher plane than any politician."-- Charlie Chaplin
Report Abuse
smurf279 is not online. smurf279
Joined: 15 Mar 2010
Total Posts: 6871
24 May 2012 05:34 PM
Tip:

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; X; X-1; X-1; X=1; X-1; X; X+1}
Y = {Y+1; Y+1; Y+1; Y; Y; Y-1; Y-1; Y-1};
}
end

Storing a table for X values and Y values is much more memory effecient than the alternative of storing a table for each ordered pair. This especially comes in handy when generating lists of coordinates like what you seem to be doing ^.^
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