[Trigger] Loops (limited!) causing some kind of overload?

Hugget Sukker · Jun 24, 2009

This is not about the program crashing.

I use a couple arrays in a map. One called TilePoint (a point array) and one called TileValue (an integer array). Their sizes are now both set to 1681; because that's the maximum number of "tiles" I use (imaginary squares of size 128 x 128). TilePoint refers to the center of each tile, while TileValue is a value I assign to each tile, which can range from -2 to (Range). Range is used by many triggers in the map to calculate the number of tiles we are currently operating with.

The heaviest trigger in my map is a loop, in a loop, in a loop, in a loop, in a looping trigger, set to run until a variable becomes >= Range.
With this trigger, I run into a problem I can't solve. The trigger itself works perfectly, until I try to set Range (integer) to 18+. Then it won't get to the end of the trigger. A game message is supposed to report how many times the trigger has looped afterwards, and the textMessage doesn't show when Range >= 18.

I'm not going to write the whole trigger here because of its length

Why does it stop responding when I set a certain integer to 18 or higher? Is it some kind of limit that makes WC3 simply ignore the functions? Earlier the maximum were 6, now, after a bit of rewriting, it's 17. It's weird...
Is it simply because tons of conditions and actions being repeated referring to different locations and all, say about 6000 times in the trigger, is too heavy? Rep if you know what's causing this prob

Reaper2008 · Jun 24, 2009

Check your math, also if you're changing arrays be sure that their index <= 8192.

GhostWolf · Jun 24, 2009

You probably made a lock by mistake. By a lock I mean you made a condition that cannot happen.

Hugget Sukker · Jun 24, 2009

But there are no conditions before the text message. It disappears. All actions at the end of the trigger seem to disappear, even though no conditions are required for those actions.

Storyyeller · Jun 24, 2009

I've heard there is a built in execution limit per thread to try to stop infinite loops, but you can get around it using ExecuteFunc() to start a new thread.

Hugget Sukker · Jun 24, 2009

I mainly understand what you are saying, but I don't really know what ExecuteFunc is. Is that costom script? I never really dug into that part. Guess I should look around here to learn some of the things I haven't found out myself.

Coolty44 · Jun 24, 2009

If your trigger is in GUI, click on it, right-click the thing above Events and select Copy as Text. Then put it in trigger tags so we can help better

Hugget Sukker · Jun 24, 2009

Fine. I had to get it on a different computer. It started to work fine after some rewriting. Unfortunately, I only have the oldest and the newest. I don't have the one where you can see the real difference that made it work. There are a lot of things wrong with the first one. I still haven't figured out what exactly was wrong.

FLOODER PREPERATION: Don't have the old one of this, which was not-working trigger's trusty sidekick.

FlooderPrep
- Events
- Conditions
- Actions
  - Set Checkpoint = (Point((Real((((Integer((X of (Position of TurnDummy)))) / 128) x 128))), (Real((((Integer((Y of (Position of TurnDummy)))) / 128) x 128)))))
  - If (All Conditions are True) then do (Then Actions) else do (Else Actions)
    - If - Conditions
      - (X of (Checkpoint)) Greater than or equal to 0.00
    - Then - Actions
      - Set Checkpoint = (Checkpoint offset by (64.00, 0.00))
    - Else - Actions
      - Set Checkpoint = (Checkpoint offset by (-64.00, 0.00))
  - If (All Conditions are True) then do (Then Actions) else do (Else Actions)
    - If - Conditions
      - (Y of (Checkpoint)) Greater than or equal to 0.00
    - Then - Actions
      - Set Checkpoint = (Checkpoint offset by (0.00, 64.00))
    - Else - Actions
      - Set Checkpoint = (Checkpoint offset by (0.00, -64.00))
  - Set corner = (Checkpoint offset by ((Real((0 - ((Range - 1) x 128)))), (Real((0 - ((Range - 1) x 128))))))
  - Set p = 0
  - For each (Integer B) from 1 to Rear, do (Actions)
    - Loop - Actions
      - For each (Integer A) from 1 to Rear, do (Actions)
        
        Loop - Actions
        
        Set p = (p + 1)
        
        Set BoardPoint = (corner offset by ((Real(((Integer A) x 128))), (Real(((Integer B) x 128)))))
        
        Set TileValue = -1
  - Set TileValue[((Rear x Range) + (Range + 1))] = 0
  - Set n = 0
  - Trigger - Run New Flooder <gen> (checking conditions)
  - Game - Display to (All players) the text: Yaouahmogamatzughaa...

FLOODER (BEFORE): Not-working version.

Flooder
- Events
- Conditions
  - n Less than Range
- Actions
  - Set n = (n + 1)
  - For each (Integer B) from 1 to Rear, do (Actions)
    - Loop - Actions
      - For each (Integer A) from 1 to Rear, do (Actions)
        
        Loop - Actions
        
        Set p = ((Integer A) + (((Integer B) - 1) x Rear))
        
        If (All Conditions are True) then do (Then Actions) else do (Else Actions)
        
        If - Conditions
        
        TileValue Equal to -1
        
        Or - Any (Conditions) are true
        
        Conditions
        
        ((Units in (Region centered at BoardPoint with size (128.00, 128.00)) matching (((Matching unit) is alive) Equal to True)) is empty) Equal to True
        
        ((Units in (Region centered at BoardPoint with size (128.00, 128.00)) matching (((Matching unit) belongs to an enemy of (Owner of TurnDummy)) Equal to True)) is empty) Equal to True
        
        ((Units in (Region centered at BoardPoint with size (128.00, 128.00)) matching (((Matching unit) is A peon-type unit) Equal to False)) is empty) Equal to True
        
        (TurnDummy is A flying unit) Equal to True
        
        Or - Any (Conditions) are true
        
        Conditions
        
        (Terrain pathing at BoardPoint of type Walkability is off) Equal to False
        
        And - All (Conditions) are true
        
        Conditions
        
        (TurnDummy is A flying unit) Equal to True
        
        (Terrain pathing at BoardPoint of type Flyability is off) Equal to False
        
        Then - Actions
        
        For each (Integer localY) from -1 to 1, do (Actions)
        
        Loop - Actions
        
        For each (Integer localX) from -1 to 1, do (Actions)
        
        Loop - Actions
        
        Set t = (((Integer A) + localX) + ((((Integer B) + localY) - 1) x Rear))
        
        If (All Conditions are True) then do (Then Actions) else do (Else Actions)
        
        If - Conditions
        
        t Greater than 0
        
        t Less than Size
        
        TileValue[t] Equal to (n - 1)
        
        Or - Any (Conditions) are true
        
        Conditions
        
        And - All (Conditions) are true
        
        Conditions
        
        (Terrain pathing at (BoardPoint offset by (((Real(localX)) x 128.00), 0.00)) of type Walkability is off) Equal to True
        
        (Terrain pathing at (BoardPoint offset by (0.00, ((Real(localY)) x 128.00))) of type Walkability is off) Equal to True
        
        And - All (Conditions) are true
        
        Conditions
        
        (Terrain pathing at (BoardPoint offset by (((Real(localX)) x 128.00), 0.00)) of type Flyability is off) Equal to True
        
        (Terrain pathing at (BoardPoint offset by (0.00, ((Real(localY)) x 128.00))) of type Flyability is off) Equal to True
        
        (TurnDummy is A flying unit) Equal to True
        
        Then - Actions
        
        If (All Conditions are True) then do (Then Actions) else do (Else Actions)
        
        If - Conditions
        
        Or - Any (Conditions) are true
        
        Conditions
        
        ((Units in (Region centered at BoardPoint with size (128.00, 128.00)) matching ((Unit-type of (Matching unit)) Equal to Difficult Terrain)) is empty) Equal to True
        
        (TurnDummy is A flying unit) Equal to True
        
        Then - Actions
        
        Set TileValue = n
        
        Else - Actions
        
        Set TileValue = (n + 1)
        
        Else - Actions
        
        Else - Actions
  - Trigger - Run (This trigger) (checking conditions)

I ask if a square contains a peon-type unit, because I use dummies of such names as Difficult Terrain and Landmine, which are classified as workers to seperate them from real combatants.

FLOODER (AFTER): Final, working version.

New Flooder
- Events
- Conditions
  - n Less than Range
- Actions
  - Set n = (n + 1)
  - Set p = 0
  - For each (Integer B) from 1 to Rear, do (Actions)
    - Loop - Actions
      - For each (Integer A) from 1 to Rear, do (Actions)
        
        Loop - Actions
        
        Set p = (p + 1)
        
        If (All Conditions are True) then do (Then Actions) else do (Else Actions)
        
        If - Conditions
        
        TileValue Equal to (n - 1)
        
        Then - Actions
        
        For each (Integer localY) from -1 to 1, do (Actions)
        
        Loop - Actions
        
        For each (Integer localX) from -1 to 1, do (Actions)
        
        Loop - Actions
        
        Set t = (p + ((localY x Rear) + localX))
        
        If (All Conditions are True) then do (Then Actions) else do (Else Actions)
        
        If - Conditions
        
        (t Greater than 0) and (t Less than or equal to Size)
        
        ((Playable map area) contains BoardPoint[t]) Equal to True
        
        TileValue[t] Equal to -1
        
        (BoardPoint[t] is masked for (Owner of TurnDummy)) Equal to False
        
        Or - Any (Conditions) are true
        
        Conditions
        
        ((Units in (Region centered at BoardPoint[t] with size (128.00, 128.00)) matching (((Matching unit) is alive) Equal to True)) is empty) Equal to True
        
        ((Units in (Region centered at BoardPoint[t] with size (128.00, 128.00)) matching (((Matching unit) is A peon-type unit) Equal to False)) is empty) Equal to True
        
        ((Units in (Region centered at BoardPoint[t] with size (128.00, 128.00)) matching (((Matching unit) belongs to an enemy of (Owner of TurnDummy)) Equal to True)) is empty) Equal to True
        
        (TurnDummy is A flying unit) Equal to True
        
        Or - Any (Conditions) are true
        
        Conditions
        
        (Terrain pathing at Boardpoint(t) of type Walkability is off) Equal to False
        
        And - All (Conditions) are true
        
        Conditions
        
        (TurnDummy is A flying unit) Equal to True
        
        (Terrain pathing at Boardpoint(t) of type Flyability is off) Equal to False
        
        Then - Actions
        
        Set TileValue[t] = n
        
        Else - Actions
        
        Else - Actions
  - Trigger - Run (This trigger) (checking conditions)

And what this does is make a kind of flood fill for a tilebased game to find the fastest path to something. Blizzard's own unit movement works fine, but I'm using turn-based tabletop style movement, and I want to show a little graphical walking path for the player too, so this hellishness is necesarry.

Storyyeller · Jun 24, 2009

ExecuteFunc() is a JASS native that allows you to call a function by name (as a string)
I think you'll have to do Custom Script if you want to use it though

Also, have you tried using a different search algorithm? In my experience, something is simple as changing the algorithm can lead to million-fold improvements.

If you explain exactly what you need, I could try to write you a better one.

Hugget Sukker · Jun 24, 2009

Your turn starts. Where can you go? Must know before you click somewhere, because that's faster. You can try a million places, but you just need to check where you can go once per move during your turn. Now we must check each tile within whatever area we choose. I use squares of 128 x 128, because that's the counting unit for map sizes, and the scales of the grid in the editor, and most doodads and other things that block pathing. I need to know where I can go and how many squares I must cross to get there. We count diagonally around squares with enemy units, but not cliffs or squares that are blocked by doodads. My idea here is to assign each free square with a value giving the movement distance from the unit to the target counted in squares. So we make a kind of flood fill with (more or less) unlimited colors. A sunburst. The assigned value tells the color nuance of the square.

Also, have you tried using a different search algorithm? In my experience, something is simple as changing the algorithm can lead to million-fold improvements.

I have tried a couple things. I'm not that good at it right now. This took time. But this is also what worked best so far.

Storyyeller · Jun 25, 2009

So are you trying to find the shortest path to a specific square, or are you trying to find all possible squares that are within a certain distance?

Storyyeller · Jun 25, 2009

This part doesn't look right

Or - Any (Conditions) are true
- Conditions
  - ((Units in (Region centered at BoardPoint with size (128.00, 128.00)) matching (((Matching unit) is alive) Equal to True)) is empty) Equal to True
  - ((Units in (Region centered at BoardPoint with size (128.00, 128.00)) matching (((Matching unit) belongs to an enemy of (Owner of TurnDummy)) Equal to True)) is empty) Equal to True
  - ((Units in (Region centered at BoardPoint with size (128.00, 128.00)) matching (((Matching unit) is A peon-type unit) Equal to False)) is empty) Equal to True
  - (TurnDummy is A flying unit) Equal to True

Also, you've got tons of leaks, and you forgot to set udg_n.

Hugget Sukker · Jun 25, 2009

Both. Since you can click almost anywhere to know the distance to that place, why not map each square and its walking distance. But what you've seen does not involve finding the quickest path, only mapping the paths.

Tons of leaks? udg_n? Don't know what you're... okay I get the growing impression that I'm more than what you call... noob... in this area... more than I thought. Noob, green, like a peon left naked in Ashenvale forest.
If you will have me excused for expressing myself a bit comically, and maybe a little tragic too: I ain't never had use of no leak or no udg_thingamadong! I just write plain and simple like you can see up there, and it's never caused me a single problem that couldn't be fixed...withOUT using weird thingies on sticks.

So, what are you suggesting? That I make unit group variables for Units in (Region centered at BoardPoint(p) with... etc. etc. And destroy them after use? I think I better, as said earlier, go learn about the thingies on long sticks myself, and not post any homemades before I know what thingies on sticks are, how they're used, and why I should use them.

dimitri231 · Jun 25, 2009

These triggers doesnt have an event.

Storyyeller · Jun 25, 2009

Well if you want to find all possible destinations, I can't think of any method better then floodfill. You could still probably benefit by rewriting everything in JASS though.

Hugget Sukker · Jun 25, 2009

Hey thanks Storyyeller. You made me read totorials, and I'm getting wiser already. Rewriting everything in JASS is a bit hard for me now. When I understand JASS a little better, I can start doing that. Need to read totorials first.

Edit: Oh, and about "all possible destinations". Well I can't see other ways of finding the quickest path than to find all possible destinations first. Or you could let a dummy walk the path first, but that's going to take way too long.

dimitri231 said:
These triggers doesnt have an event.

No, but I have other trigger that refer to them. I have a silly error though. In the first trigger, I've used an EventResponse.

Storyyeller · Jun 25, 2009

Finding the fastest path to a given point is much faster and easier then finding all possible paths.

Storyyeller · Jun 25, 2009

Here's what I came up with as an example

JASS:

globals
    constant integer WIDTH //put the width of your sqaure array here
    integer array fx
    integer array gx
    integer array cx
    integer lastptr
endglobals

function DebugMsg takes string s returns nothing
    call DisplayTextToPlayers(GetLocalPlayer(),0,0,s)    
endfunction

//-----------------------------------------------------
// Heap managing code

function HeapSwap takes integer i, integer j returns nothing
    //Swaps the heap entries at positions i and j
    local integer tempc = cx[i]
    local integer tempf = fx[i]
    local integer tempg = gx[i]
    set fx[i] = fx[i]
    set gx[i] = gx[i]
    set cx[i] = cx[i]
    set fx[j] = tempf
    set gx[j] = tempg
    set cx[j] = tempc      
endfunction

function PrepareHeap takes integer c0, integer f0 returns nothing
    local integer i=1
    set fx[0] = f0
    set gx[0] = 0
    set cx[0] = c0
    loop
        exitwhen i>=8191
        set fx[i]=-1
        set gx[i]=-1
        set cx[i]=-1
        set i=i+1
    endloop
    set lastptr=1
endfunction

function HeapInsert takes integer newc, integer newf, integer newg returns nothing
    local integer childptr = lastptr
    local integer parentptr = (lastptr-1)/2
    
    if lastptr>8191 then
        call DebugMsg("Error: Pathfinding failed. Maximum heap size exeeded.")
        return
    endif
    
    set fx[lastptr] = newf
    set gx[lastptr] = newg
    set cx[lastptr] = newc
    set lastptr=lastptr+1
    
    loop
        exitwhen fx[parentptr] <= fx[childptr]    
                
        //swap and continue
        call HeapSwap( childptr, parentptr )   
        
        set childptr = parentptr
        set parentptr = (parentptr - 1)/2              
    endloop    
endfunction

function HeapRemove takes nothing returns nothing
    local integer parentptr = 0
    local integer childptr = 2
    local integer tempc
    local integer tempf
    local integer tempg


    if lastptr==1 then
        call DebugMsg("Error: Pathfinding failed. No candidate nodes left.")
        return
    endif   
     
    set lastptr = lastptr - 1
    
    set fx[0]=fx[lastptr]
    set gx[0]=gx[lastptr]
    set cx[0]=cx[lastptr]
    set fx[lastptr] = -1        //show that this spot is now invalid
    
    loop
        exitwhen fx[childptr] == -1    
                
        //check the right child first
        if fx[childptr] < fx[parentptr] then
            call HeapSwap( parentptr, childptr )   
        //then the left child  
        elseif fx[childptr-1] < fx[parentptr] then
            set childptr = childptr - 1
            call HeapSwap( parentptr, childptr )
        else
            return //if both children are ok we can stop
        endif        

        set parentptr = childptr         
        set childptr = childptr * 2 + 2
    endloop    
endfunction

//-----------------------------------------------------
// Pathfinding code

function IsAllowed takes integer c returns boolean
    //can this square be walked upon?
    return true
endfunction 

function LowerBound takes integer c1, integer c2 returns integer
    //Returns the direct distances between two squares
    local integer y1 = c1/WIDTH
    local integer x1 = c1 - y1 * WIDTH 
    local integer y2 = c2/WIDTH
    local integer x2 = c2 - y2 * WIDTH         
    local integer dist = -1
    
    if y2-y1 > dist then
        set dist = y2-y1
    endif
    if y1-y2 > dist then
        set dist = y1-y2
    endif
    if x2-x1 > dist then
        set dist = x2-x1
    endif
    if x1-x2 > dist then
        set dist = x1-x2
    endif    

    return dist
endfunction

function NewNode takes integer dest, integer oldg, integer oldc, integer dx, integer dy returns nothing
    local integer newc = oldc + dx + dy * WIDTH
    if IsAllowed(newc) then
        call HeapInsert( newc, oldg + 1 + LowerBound( newc, dest), oldg + 1)
    endif
endfunction

function PathFinder takes integer origin, integer dest returns integer
    //returns the shortest distance between two squares. Can be easily modified to find the shortest path instead
    
    local integer oldc
    local integer oldf
    local integer oldg        
    
    call PrepareHeap( origin, LowerBound( origin, dest) )
    
    loop
        if cx[0]==dest then
            return gx[0]
        endif
        
        set oldc=cx[0]
        set oldf=fx[0]
        set oldg=gx[0]
        
        call NewNode( dest, oldg, oldc, -1, -1)  
        call NewNode( dest, oldg, oldc, -1, 0)  
        call NewNode( dest, oldg, oldc, -1, 1)  
        call NewNode( dest, oldg, oldc, 0, 1)  
        call NewNode( dest, oldg, oldc, 1, 1)  
        call NewNode( dest, oldg, oldc, 1, 0)  
        call NewNode( dest, oldg, oldc, 1, -1)  
        call NewNode( dest, oldg, oldc, 0, -1) 
        
        call HeapRemove() 
        
    endloop
    //if execution reaches this point, something wrong happened
    return -1      
endfunction

Hugget Sukker · Jun 25, 2009

Yell me something nice. It's a bit confusing for me right now. But it looks sort of like something I've tried in GUI, which I failed to make work. But am I right that you will have to check an amount of locations first to see if there is pathing and count the distance before you can find the quickest path, but you stop checking the area when you reach the destination?

It'll take me awhile to understand all this. Could you maybe break down what your code exactly does? In which order does it check things? Why do I need to return the direct distance between two squares?

Storyyeller · Jun 25, 2009

It uses an algorithm called A* (I learned about it from Wikipedia)

Basically, you maintain a list of nodes remaining to be checked, along with the total distance traveled to reach them and the estimated distance to the destination from that point.

In each step, you find the node on the list which has the smallest estimated total
Add the neighbors to the list, and remove the original from the list

When the destination appears as the node with the smallest total, you know you've found the shortest possible path.

Most of the code I posted has to deal with adding and removing nodes from the list. The actual pathfinding part is pretty short.

Hugget Sukker said:
Why do I need to return the direct distance between two squares?

It is the method used to estimate the distance remaining, so that the candidates can be ordered correctly. Also known as a heuristic.

Edit: I improved the code a bit and rearranged it to make more sense
Of course it would be nice if the forum software actually displayed it correctly too.

Hugget Sukker · Jun 25, 2009

Hmm... Ok so how do we (in English) find the total distance traveled to reach each node and the estimated distance to the destination (Edit: from that point) - without floodfilling or something similar?

Edit: I got that we counted direct distance between each square. But I don't understand, which order do we check things in? From origin and outwards, right? And then we store nodes that aren't checked and nodes that are checked seperated? Checking from side to side, X loop within Y loop? Or just a list of place we haven't checked, and we start with those adjacent (no coordinates involved)?

Edit: Can't find anything about A*.

Edit: Found it, I think I'm beginning to understand. Gonna play with it a little.

Storyyeller · Jun 25, 2009

Here's the Wikipedia article
http://en.wikipedia.org/wiki/A*_search_algorithm

Here's a short example to hopefully show how it works
Suppose we want to find the shortest path from 0,0 to 2,3,
with obstacles at 0,1 1,1 2,1 1,2 with everywhere else walkable

Our list has the following format
x/y/distance traveled so far/ estimated distance left/ total estimate

At the start, our list looks like this
0 0 0 3 3

-1 0 1 3 4
-1 1 1 3 4
1 0 1 3 4
-1 -1 1 4 5
0 -1 1 4 5
1 -1 1 4 5

-1 1 1 3 4
1 0 1 3 4
-1 -1 1 4 5
0 -1 1 4 5
1 -1 1 4 5
-1 1 2 3 5
0 0 2 3 5
-2 -1 2 4 6
-2 0 2 4 6
-2 1 2 4 6
-1 -1 2 4 6
0 -1 2 4 6

1 0 1 3 4
0 2 2 2 4
-1 -1 1 4 5
0 -1 1 4 5
1 -1 1 4 5
-1 1 2 3 5
0 0 2 3 5
-1 0 2 3 5
-1 2 2 3 5
0 0 2 3 5
-2 -1 2 4 6
-2 0 2 4 6
-2 1 2 4 6
-1 -1 2 4 6
0 -1 2 4 6
-2 0 2 4 6
-2 1 2 4 6
-2 2 2 4 6

0 2 2 2 4
-1 -1 1 4 5
0 -1 1 4 5
1 -1 1 4 5
-1 1 2 3 5
0 0 2 3 5
-1 0 2 3 5
-1 2 2 3 5
0 0 2 3 5
-2 -1 2 4 6
-2 0 2 4 6
-2 1 2 4 6
-1 -1 2 4 6
0 -1 2 4 6
-2 0 2 4 6
-2 1 2 4 6
-2 2 2 4 6
0 0 3 3 6
2 0 3 3 6
0 -1 3 4 7
1 -1 3 4 7
2 -1 3 4 7

Storyyeller · Jun 25, 2009

1 3 3 1 4
-1 -1 1 4 5
0 -1 1 4 5
1 -1 1 4 5
-1 1 2 3 5
0 0 2 3 5
-1 0 2 3 5
-1 2 2 3 5
0 0 2 3 5
0 3 3 2 5
-2 -1 2 4 6
-2 0 2 4 6
-2 1 2 4 6
-1 -1 2 4 6
0 -1 2 4 6
-2 0 2 4 6
-2 1 2 4 6
-2 2 2 4 6
0 0 3 3 6
2 0 3 3 6
-1 1 3 3 6
-1 2 3 3 6
-1 3 3 3 6
0 -1 3 4 7
1 -1 3 4 7
2 -1 3 4 7

2 3 4 0 4
-1 -1 1 4 5
0 -1 1 4 5
1 -1 1 4 5
-1 1 2 3 5
0 0 2 3 5
-1 0 2 3 5
-1 2 2 3 5
0 0 2 3 5
0 3 3 2 5
1 4 4 1 5
2 2 4 1 5
2 4 4 1 5
-2 -1 2 4 6
-2 0 2 4 6
-2 1 2 4 6
-1 -1 2 4 6
0 -1 2 4 6
-2 0 2 4 6
-2 1 2 4 6
-2 2 2 4 6
0 0 3 3 6
2 0 3 3 6
-1 1 3 3 6
-1 2 3 3 6
-1 3 3 3 6
0 2 4 2 6
0 3 4 2 6
0 4 4 2 6
0 -1 3 4 7
1 -1 3 4 7
2 -1 3 4 7

Hugget Sukker · Jun 25, 2009

Hmmm... Well, thanks. I'm kinda running outta coal here. I gotta illustrate it for myself before I can understand it. My head isn't built for x's and y's you know

Gotta try it out once I get my coal refill. But thanks for all your help Storyyeller. Gave you rep right? Be communicating in some kind of future

Storyyeller · Jun 25, 2009

Sorry, my explanation isn't very explanatory

The best way to understand it would be an animated visual diagram

Hugget Sukker · Jun 26, 2009

I'm thinking that maybe my old idea was better for its purpose in my game. It's turn-based first. No movement in the map can slow things down because only one unit can move at the time, and creeps who aren't in the ActiveCombatants unit group only pick their noses and drip spittle out of their gaping maws (not getting their turns).

When it's your turn, and you are standing still, this is active: You click somewhere! If target location is blocked by something, masked for you, or outside the map, you get an immediate No-go message. If not, we check how long your voyage to that location is and find the exact path. Then I think this would work fastest:
We map out your whole pathable vicinity and each square's voyage cost for you once per action, the first time you click somewhere. Second time you click at a new location, we use the old data. The only thing we need to check when you click the second, third, fourth, etc. times is the path, which is quickly found once everything is mapped out with relative voyage costs to locations and all.
All I need to do is make sure the whole thing doesn't leak like hell, which I have been a fool to so far. And also, I shouldn't use a point array when all required in order to know the locations is an integer array:

RealY = (LocInt(t) / Width)
RealX = (LocInt(t) - (RealY x Width))
//or something like that with some adjustments. Don't blame me if it's totally broken.

The idea is just to convert an integer into two coordinates.

Besides, how does A* know where to put each node? Doesn't that become tough on it when it has to be so dynamic? Sorry, it might be stupid of me to critizise something I don't entirely understand (e.g. the upper part of your script - I think).

Edit: No. Scrap the last comment. No, no. It's actually just the same. You can map out all the stuff with either method. Only, with the modified floodfill you can find the path very quickly by mapping out everything with travel costs ahead of need. The pathfinding part itself is done in a flash and easilly when you already know the cost of each square. You go from destination to any square with a lower cost until you reach the origin unit, and there you have the path.

Storyyeller · Jun 26, 2009

First off, there's no need to store the coordinates for the center of each square, since it's just a simple formula

As for A* vs Floodfill, well I haven't actually seen the map. You know more about the situation then me.
You'll still have to remove the leaks and optimize it a bit of course.

Hugget Sukker · Jun 26, 2009

I need to know which square is which. And, as I said myself and agree with you in, the coordinates don't matter, yet the squares must have a number that can be translated into coordinates and vice versa, by knowing the center and width of my entire checked area. Square number 7 equals 4, for instance. So the squares are represented in an integer array. Square(7) == 4. I can pick out a point on my board, translate its coordinates into an integer "t", and thus refer to Square(t) when I need to know the cost of a specific square. Square(t) == 9, so 9 is the cost to go there.

I haven't seen the map either, or rather, there is no map yet. Just a big, blank, flat terrain with a few test subjects and test obstacles placed randomly. It's meant to be a game concept used in multiple maps. I don't know if you've played tabletop RPG's such as D&D. The same system is here for movement. Unlike most RPGs I know, EVERYTHING here is turn-based. It's constant "action", and there's no rest long enough to swap out of turn-mode. Even dialogue, semi-cinematic story events, and quest briefings may happen in turn-mode.

So, with Action Points also there, it's basically a mixture of common hack'n'slash, classic Fallout, and Heroes of Might & Magic (except players cooperate and don't have a tower/dungeon/palace/whatever). It's a very un-warcraftish concept. I'm trying to create twist from WC3 that isn't meant to exist. I should write about my project at Map Development.

Storyyeller · Jun 26, 2009

Well good luck

[Trigger] Loops (limited!) causing some kind of overload?

Similar threads