# Grid "system", useful or not ? :S

#### saw792

##### Is known to say things. That is all.
Big O notation (eg: O(1), O(n), O(n^2), O(log n) etc) is a way you can represent the complexity of an algorithm or operation, in other words how well it scales.

For example, right now every time getPointGridSquare is called it will run the code inside the loop once for every square until it finds the correct square. That's called a linear search, i.e. you search through every element until one satisfies the condition in counting order. This means that with a grid of n squares it will take on average n/2 time to find the correct square (sometimes over, sometimes under). Thus the amount of time it takes for your algorithm to find the correct square increases linearly with an increase in the number of squares on the grid. So if you double the number of squares you double the (average) amount of time it takes for your code to run. Thus O(n) is used to describe your algorithm as it is a linear relationship between time to run and number of squares.

My approach is to find a mathematical way of calculating which square the coordinates will be in. This means that regardless of the number of grid squares in the grid it will take the same amount of time to find the correct square. Thus an algorithm of that sort would be O(1), as the time taken is constant regardless of the number of grid squares n.

EDIT: getPointGridSquare:
JASS:
``````method getPointGridSquare takes real xcoord, real ycoord returns GridSquare
local real x0 = centerX - (width/2.0)
local real y0 = centerY + (height/2.0)
return getSquare(R2I((xcoord - x0)/squareWidth), R2I((ycoord - y0)/squareheight))
endmethod``````

Oh and your getSquare method should have some error checking to make sure the coordinates actually exist in the grid. That way getPointGridSquare doesn't need to duplicate the checks.

#### Komaqtion

##### You can change this now in User CP.
Big O notation (eg: O(1), O(n), O(n^2), O(log n) etc) is a way you can represent the complexity of an algorithm or operation, in other words how well it scales.

For example, right now every time getPointGridSquare is called it will run the code inside the loop once for every square until it finds the correct square. That's called a linear search, i.e. you search through every element until one satisfies the condition in counting order. This means that with a grid of n squares it will take on average n/2 time to find the correct square (sometimes over, sometimes under). Thus the amount of time it takes for your algorithm to find the correct square increases linearly with an increase in the number of squares on the grid. So if you double the number of squares you double the (average) amount of time it takes for your code to run. Thus O(n) is used to describe your algorithm as it is a linear relationship between time to run and number of squares.

My approach is to find a mathematical way of calculating which square the coordinates will be in. This means that regardless of the number of grid squares in the grid it will take the same amount of time to find the correct square. Thus an algorithm of that sort would be O(1), as the time taken is constant regardless of the number of grid squares n.

Thanks for this explanation (Although Bribe already threw me a PM explaning this already XD) it was very helpful !

EDIT: getPointGridSquare:

JASS:
``````method getPointGridSquare takes real xcoord, real ycoord returns GridSquare
local real x0 = centerX - (width/2.0)
local real y0 = centerY + (height/2.0)
return getSquare(R2I((xcoord - x0)/squareWidth), R2I((ycoord - y0)/squareheight))
endmethod``````

Shouldn't that inline ?

Oh and your getSquare method should have some error checking to make sure the coordinates actually exist in the grid. That way getPointGridSquare doesn't need to duplicate the checks.

Well, 'getSquare' will just return 0 as the GridSquare struct if it doesn't exist, wouldn't it ? :S

#### Bribe

##### vJass errors are legion
Shouldn't that inline ?

That won't inline because the "invisible" variable "this" is referenced more than once.

#### Komaqtion

##### You can change this now in User CP.
Ok, well I haven't really understood what inlining means XD
Does:
JASS:
``````    method getSquare takes integer xCount, integer yCount returns GridSquare
return LoadInteger( Hashtable, this, ( yCount * heightSquares ) + xCount )
endmethod``````

that inline ?

And also:

Well, 'getSquare' will just return 0 as the GridSquare struct if it doesn't exist, wouldn't it ? :S

#### Bribe

##### vJass errors are legion
JASS:
``````
method getSquare takes integer xCount, integer yCount returns GridSquare
return LoadInteger(Hashtable, this, yCount * this.heightSquares + xCount)
endmethod``````

"this" is referenced twice. Any parameters can only be referenced once.
JASS:
``````
method guy takes nothing returns nothing
local integer i=0
call DoNothing()
endmethod``````

In the above example, "this" is not even referenced, though it would not inline, because there are two lines of code.
JASS:
``````
method return0 takes nothing returns integer
return 0
endmethod
//
set this = return0()``````

The above example inlines, as it has only one line and it does not reference any parameters more than once.

#### Komaqtion

##### You can change this now in User CP.
Oh, ok Thanks

Ok, this is what I have atm, is it good ?
JASS:
``````library Gridder

globals
public hashtable Hashtable
endglobals

private keyword Grid

struct GridSquare
real centerX
real centerY
real width
real height

real maxX
real minX
real maxY
real minY

Grid squareOwner
integer squareNumber

//effect array outlineSFX [8190]

static method create takes real CenterX, real CenterY, real Width, real Weight, Grid owner returns thistype
local thistype this = thistype.allocate()

set centerX = centerX
set centerY = centerY
set width = width
set height = height

set maxX = centerX + (width / 2)
set minX = centerX - (width / 2)
set maxY = centerY + (height / 2)
set minY = centerY - (height / 2)

set squareOwner = owner

return this
endmethod

method outlineSquare takes integer lineEffects, string whichEffect returns nothing

endmethod

endstruct

struct Grid
real centerX = 0.
real centerY = 0.
real width = 0.
real height = 0.
real squareWidth = 0.
real squareHeight = 0.

integer numberSquares = 0
integer heightSquares = 0
integer widthSquares = 0

static method create takes real x, real y, integer h_number, integer w_number, real squarewide, real squarehigh returns thistype
local thistype this = thistype.allocate()
local integer i = 0
local integer i1 = 0
local integer square_count = -1
local real curX = 0.
local real curY = 0.
local real startX = x - ((squarewide * h_number) / 2.)
local real startY = y + ((squarehigh * w_number) / 2.)
local GridSquare square

set centerX = x
set centerY = y
set width = h_number * squarewide
set height = w_number * squarehigh
set numberSquares = h_number * w_number
set squareWidth = squarewide
set squareHeight = squarehigh
set heightSquares = h_number
set widthSquares = w_number

loop
set i = i + 1
set i1 = 0

exitwhen i &gt; w_number

set curY = startY - (squarehigh * i)

loop
set i1 = i1 + 1
set square_count = square_count + 1

exitwhen i1 &gt; h_number

set curX = startX + (squarewide * i1)
set square = GridSquare.create( curX, curY, squarewide, squarehigh, this )

call SaveInteger( Hashtable, this, square_count, square )
endloop

endloop

return this
endmethod

method getPointGridSquare takes real xcoord, real ycoord returns GridSquare
local real x0 = centerX - (width/2.0)
local real y0 = centerY + (height/2.0)

return getSquare(R2I((xcoord - x0)/squareWidth), R2I((ycoord - y0)/squareHeight))
endmethod

method getSquare takes integer xCount, integer yCount returns GridSquare
return LoadInteger( Hashtable, this, ( yCount * heightSquares ) + xCount )
endmethod

method onDestroy takes nothing returns nothing
local integer i = -1
local GridSquare square = 0

loop
set i = i + 1
exitwhen i &gt;= numberSquares

set square = LoadInteger( Hashtable, this, i )

call square.destroy()
endloop

call FlushChildHashtable( Hashtable, this )
endmethod

private static method onInit takes nothing returns nothing
debug local thistype this
debug local GridSquare square

set Hashtable = InitHashtable()

debug set square = getPointGridSquare( -562., 153 )
debug set this = thistype.create( 0., 0., 10, 10, 150., 150. )
debug call DestroyEffect( AddSpecialEffect( &quot;Abilities\\Spells\\Human\\Thunderclap\\ThunderClapCaster.mdl&quot;, square.centerX, square.centerY ) )
endmethod

endstruct

endlibrary``````

#### saw792

##### Is known to say things. That is all.
Yeah it will return 0, but 0 also refers to a valid grid square...

#### Komaqtion

##### You can change this now in User CP.
It returns the entire struct, not the number it is in the grid, so a struct's value can't be 0, right ?

#### saw792

##### Is known to say things. That is all.
Yeah you're right I was thinking of the input to LoadInteger not what the data is.

It's ok

#### Komaqtion

##### You can change this now in User CP.
So, what do you think, is this good, or better yet is it good enough for an approvable resource ?
(Though personally I think it has way too few features, so I would be glad to hear some ideas for them )

And I also added a method to the GridSquare struct:
[ljass]method outlineSquare takes integer lineEffects, string whichEffect returns nothing[/ljass]

Which is supposed outline the targetted square with effects by using some maths and such but I can't find a good way of doing this without making those effects leak as I can't store them in a variable... :S
Should I just use the hashtable again here, or what do you think ?

JASS:
``````library Gridder

globals
public hashtable Hashtable
endglobals

private keyword Grid

struct GridSquare
real centerX
real centerY
real width
real height

real maxX
real minX
real maxY
real minY

Grid squareOwner
integer squareNumber

//effect array outlineSFX [8190]

static method create takes real CenterX, real CenterY, real Width, real Weight, Grid owner returns thistype
local thistype this = thistype.allocate()

set centerX = centerX
set centerY = centerY
set width = width
set height = height

set maxX = centerX + (width / 2)
set minX = centerX - (width / 2)
set maxY = centerY + (height / 2)
set minY = centerY - (height / 2)

set squareOwner = owner

return this
endmethod

method outlineSquare takes integer lineEffects, string whichEffect returns nothing

endmethod

endstruct

struct Grid
real centerX = 0.
real centerY = 0.
real width = 0.
real height = 0.
real squareWidth = 0.
real squareHeight = 0.

integer numberSquares = 0
integer heightSquares = 0
integer widthSquares = 0

static method create takes real x, real y, integer h_number, integer w_number, real squarewide, real squarehigh returns thistype
local thistype this = thistype.allocate()
local integer i = 0
local integer i1 = 0
local integer square_count = -1
local real curX = 0.
local real curY = 0.
local real startX = x - ((squarewide * h_number) / 2.)
local real startY = y + ((squarehigh * w_number) / 2.)
local GridSquare square

set centerX = x
set centerY = y
set width = h_number * squarewide
set height = w_number * squarehigh
set numberSquares = h_number * w_number
set squareWidth = squarewide
set squareHeight = squarehigh
set heightSquares = h_number
set widthSquares = w_number

loop
set i = i + 1
set i1 = 0

exitwhen i &gt; w_number

set curY = startY - (squarehigh * i)

loop
set i1 = i1 + 1
set square_count = square_count + 1

exitwhen i1 &gt; h_number

set curX = startX + (squarewide * i1)
set square = GridSquare.create( curX, curY, squarewide, squarehigh, this )

call SaveInteger( Hashtable, this, square_count, square )
endloop

endloop

return this
endmethod

method getPointGridSquare takes real xcoord, real ycoord returns GridSquare
local real x0 = centerX - (width/2.0)
local real y0 = centerY + (height/2.0)

return getSquare(R2I((xcoord - x0)/squareWidth), R2I((ycoord - y0)/squareHeight))
endmethod

method getSquare takes integer xCount, integer yCount returns GridSquare
return LoadInteger( Hashtable, this, ( yCount * heightSquares ) + xCount )
endmethod

method onDestroy takes nothing returns nothing
local integer i = -1
local GridSquare square = 0

loop
set i = i + 1
exitwhen i &gt;= numberSquares

set square = LoadInteger( Hashtable, this, i )

call square.destroy()
endloop

call FlushChildHashtable( Hashtable, this )
endmethod

private static method onInit takes nothing returns nothing
debug local thistype this
debug local GridSquare square

set Hashtable = InitHashtable()

debug set square = getPointGridSquare( -562., 153 )
debug set this = thistype.create( 0., 0., 10, 10, 150., 150. )
debug call DestroyEffect( AddSpecialEffect( &quot;Abilities\\Spells\\Human\\Thunderclap\\ThunderClapCaster.mdl&quot;, square.centerX, square.centerY ) )
endmethod

endstruct

endlibrary``````

#### saw792

##### Is known to say things. That is all.
Now a linked list might be useful
JASS:
``````struct GridEffect
effect e
GridEffect next = 0

static method create takes real x, real y, string path returns thistype
local thistype this = thistype.allocate
endmethod

method add takes real x, real y, path returns GridEffect
if next == 0 then
set next = thisttype.create(x, y, path)
return next
else
endif
endmethod

method onDestroy takes nothing returns nothing
call DestroyEffect(e)
call next.destroy()
endmethod
endstruct

struct GridSquare
real centerX
real centerY
real width
real height

real maxX
real minX
real maxY
real minY

Grid squareOwner
integer squareNumber

GridEffect first

static method create takes real CenterX, real CenterY, real Width, real Weight, Grid owner returns thistype
local thistype this = thistype.allocate()

set centerX = centerX
set centerY = centerY
set width = width
set height = height

set maxX = centerX + (width / 2)
set minX = centerX - (width / 2)
set maxY = centerY + (height / 2)
set minY = centerY - (height / 2)

set squareOwner = owner

return this
endmethod

method outlineSquare takes integer lineEffects, string whichEffect returns nothing
local integer i = 0
local GridEffect ge = ge.create(...)//whereever the first effect should go
set first = ge

loop
exitwhen you&#039;ve finished making effects

endloop
endmethod

method onDestroy takes nothing returns nothing
first.destroy()
endmethod

endstruct

//and ur usual grid stuff``````

It actually makes sense to do it this way this time, since you only need add/remove and not insert/read at random position in the list

#### Troll-Brain

##### You can change this now in User CP.
So, what do you think, is this good, or better yet is it good enough for an approvable resource ?

A little advice, make a ressource only if you enjoy the simple fact to make it or will use it for sure, don't attempt it will be used by other peoples, especially if it's only for theoric purposes and you even don't plan to use it yourself.

Cool != usefull.

Hmm or it's just my personal story, i dunno

#### Komaqtion

##### You can change this now in User CP.
Actually, I rarely make maps myself, and almost all of my "resources" come from questions here on the forum, though there may be just a single post which asks for something like it but if I think I can make it I'll do it

#### Troll-Brain

##### You can change this now in User CP.
It's fine as long as you enjoy making it, i just wanted to say "don't be disappointed if nobody use your resource"

#### mylemonblue

##### You can change this now in User CP.
I quickly read over the thread and still am not entirely sure what sort of grid it is (I figure it means like chess, as mentioned earleir). But can it be used to recreate games like Heroscape or Final Fantasy Tactics?

Both are grid based, and that's the first thing that came to mind when I saw the title.

*PS: Thanks for the help on the average levels thing*

#### Komaqtion

##### You can change this now in User CP.
It's fine as long as you enjoy making it, i just wanted to say "don't be disappointed if nobody use your resource"

Yeah, I know... Thanks anyways

I quickly read over the thread and still am not entirely sure what sort of grid it is (I figure it means like chess, as mentioned earleir). But can it be used to recreate games like Heroscape or Final Fantasy Tactics?

Well, I'm just giving you the battlefield layout, you may utilize it as you wish after that
I'm just not completely done with it yet as there are still some features missing (As the above mentioned outlining-problem and I also want to add a method for creating a rect in each square )

*PS: Thanks for the help on the average levels thing*

Np

General chit-chat
Help Users
• No one is chatting at the moment.
• The Helper:
I found his email and emailed him but have not heard back. I dont like it
• tom_mai78101:
Ohhh, I just came back from the airport. I'm so sorry. I was completely off grid since I left to Taiwan.
• tom_mai78101:
Here's what happened. The earthquake happened while I was high above Hawaii.
• tom_mai78101:
After landing, I got news that a big earthquake struck. Since I'm only there in Taiwan for a week, I figured the best option I have is to make sure my family is safe, and that we are all good to go from there.
• tom_mai78101:
I didn't get any phone service plans because I am mainly visiting my family and staying indoors. Well, the earthquake made me forgot to go get phone service.
• tom_mai78101:
And then a few days later, just north from my family, there was a giant plastic industrial complex that caught on fire, with the blaze burning for 1.5 days.
• tom_mai78101:
There was some air pollution and smog outside.
• tom_mai78101:
We did our Ching Ming Festival indoors with my father's family side, and occassionally traveling down southward to visit some farmlands, and paying a visit to my grandmother and my uncle on my mother's side.
• tom_mai78101:
The whole trip was quite hectic, with occasional afterquakes throughout the week. This whole time, I completely forgot about giving updates on TH. Again, sorry for the lack of communications.
• tom_mai78101:
As for Github, I often frequent there, boasting about my genetic algorithm for tools-assisted speedrunning and such. I'm also pretty active on Discord, with my tag @asperatology.
• tom_mai78101:
Yeah, the whole earthquake + air pollution combo made me completely forget about bringing updates. I'll be sure to keep on top of things after all things are less requiring my attentions.
+2
• The Helper:
I am just glad that you are OK Tom! Thank you for the update!
• Varine:
Glad to hear you're okay! I only knew about your Github cuz I tried to follow some of you when I was learning how to program, but didn't understand any of it so kind of quit paying attention to what anyone does on it
• The Helper:
Freaking storm outside is kicking!
• Blackveiled:
I wouldn't know, I'm in Joliet, Illinois right now working. I left Houston area about 2 weeks ago lol
• Blackveiled:
Not permanently of course, just a temporary job.
+1
• jonas:
• jonas:
@Blackveiled you know another word for permanent? temporary
+1
• Varine:
Briefly, he'll only be there for the interim. Like a stopgap of sorts, he'll be back home in short time
Hurray! Tom has reappeared!
• The Helper:
Happy Thursday!
• Blackveiled:
Yep. Just another fun night at work.

### Members online

No members online now.