Grid "system", useful or not ? :S

saw792

Is known to say things. That is all.
Reaction score
280
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.
Reaction score
469
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 ? :eek:

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
 

Komaqtion

You can change this now in User CP.
Reaction score
469
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 ? :eek:

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
Reaction score
67
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.
Reaction score
469
Oh, ok :D Thanks ;)

Ok, this is what I have atm, is it good ? :eek:
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 > w_number
                
                set curY = startY - (squarehigh * i)
                
                loop
                    set i1 = i1 + 1
                    set square_count = square_count + 1
                    
                    exitwhen i1 > 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 >= 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( "Abilities\\Spells\\Human\\Thunderclap\\ThunderClapCaster.mdl", square.centerX, square.centerY ) )
        endmethod
        
    endstruct
    
endlibrary
 

saw792

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

Komaqtion

You can change this now in User CP.
Reaction score
469
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.
Reaction score
280
Yeah you're right I was thinking of the input to LoadInteger not what the data is.
 

Komaqtion

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

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 > w_number
                
                set curY = startY - (squarehigh * i)
                
                loop
                    set i1 = i1 + 1
                    set square_count = square_count + 1
                    
                    exitwhen i1 > 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 >= 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( "Abilities\\Spells\\Human\\Thunderclap\\ThunderClapCaster.mdl", square.centerX, square.centerY ) )
        endmethod
        
    endstruct
    
endlibrary
 

saw792

Is known to say things. That is all.
Reaction score
280
Now a linked list might be useful :p
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
        //set e = AddSpecialEffect(...)
    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
            return next.add(x, y, path)
        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've finished making effects

                ge = ge.add(...)//wherever it goes
                
            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.
Reaction score
85
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 :p
 

Komaqtion

You can change this now in User CP.
Reaction score
469
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 :D
 

Troll-Brain

You can change this now in User CP.
Reaction score
85
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.
Reaction score
7
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.
Reaction score
469
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 :D

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 :D
 
General chit-chat
Help Users
  • No one is chatting at the moment.
  • The Helper The Helper:
    I found his email and emailed him but have not heard back. I dont like it
  • tom_mai78101 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 tom_mai78101:
    Here's what happened. The earthquake happened while I was high above Hawaii.
  • tom_mai78101 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 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 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 tom_mai78101:
    There was some air pollution and smog outside.
  • tom_mai78101 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 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. :p Again, sorry for the lack of communications.
  • tom_mai78101 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 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 The Helper:
    I am just glad that you are OK Tom! Thank you for the update!
  • Varine 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 The Helper:
    Freaking storm outside is kicking!
  • Blackveiled Blackveiled:
    I wouldn't know, I'm in Joliet, Illinois right now working. I left Houston area about 2 weeks ago lol
  • Blackveiled Blackveiled:
    Not permanently of course, just a temporary job.
    +1
  • jonas jonas:
    Glad you're ok @tom_mai78101
  • jonas jonas:
    @Blackveiled you know another word for permanent? temporary
    +1
  • Varine Varine:
    Briefly, he'll only be there for the interim. Like a stopgap of sorts, he'll be back home in short time
  • O Old Mountain Shadow:
    Hurray! Tom has reappeared!
  • The Helper The Helper:
    Happy Thursday!
  • Blackveiled Blackveiled:
    Yep. Just another fun night at work.

      The Helper Discord

      Members online

      No members online now.

      Affiliates

      Hive Workshop NUON Dome World Editor Tutorials

      Network Sponsors

      Apex Steel Pipe - Buys and sells Steel Pipe.
      Top