Gamestudio Links
Zorro Links
Newest Posts
AlpacaZorroPlugin v1.3.0 Released
by kzhao. 05/19/24 18:45
Free Live Data for Zorro with Paper Trading?
by AbrahamR. 05/18/24 13:28
Change chart colours
by 7th_zorro. 05/11/24 09:25
Data from CSV not parsed correctly
by dr_panther. 05/06/24 18:50
AUM Magazine
Latest Screens
The Bible Game
A psychological thriller game
SHADOW (2014)
DEAD TASTE
Who's Online Now
4 registered members (AndrewAMD, Ayumi, kzhao, 7th_zorro), 739 guests, and 7 spiders.
Key: Admin, Global Mod, Mod
Newest Members
Hanky27, firatv, wandaluciaia, Mega_Rod, EternallyCurious
19051 Registered Users
Previous Thread
Next Thread
Print Thread
Rate Thread
Page 4 of 4 1 2 3 4
Re: RTS Project [Re: Redeemer] #352236
01/02/11 12:10
01/02/11 12:10
Joined: Nov 2002
Posts: 913
Berlin, Germany
S
SchokoKeks Offline
User
SchokoKeks  Offline
User
S

Joined: Nov 2002
Posts: 913
Berlin, Germany
Since pointers are 32 Bit and skills (aka vars) are also 32 Bit in Gamestudio (at least until a native 64 bit version is released), you can simply store these pointers into skills without converting them to handles.
Here's an example how to save and retrieve with a cast:

Code:
myStruct* pt1; myStruct* pt2;

...

my.skill[0] = pt1;
pt2 = (myStruct*)my.skill[0];


EDIT: of course this also works with engine pointers (including ENTITY*), so there is not need to use handles for this anymore. In general C, this is considered to be a very dangerous method as pointer size can vary between platforms. For 3DGS, I'd say this is a needed hack to overcome platform limitations.

Last edited by SchokoKeks; 01/02/11 12:14.
Re: RTS Project [Re: SchokoKeks] #352310
01/02/11 20:22
01/02/11 20:22
Joined: Dec 2008
Posts: 1,660
North America
Redeemer Offline OP
Serious User
Redeemer  Offline OP
Serious User

Joined: Dec 2008
Posts: 1,660
North America
Thanks SchokoKeks, that works fine. laugh

I didn't think to do that since this method doesn't seem to work for engine objects...


Eats commas for breakfast.

Play Barony: Cursed Edition!
Re: RTS Project [Re: Redeemer] #352355
01/03/11 04:07
01/03/11 04:07
Joined: Dec 2008
Posts: 1,660
North America
Redeemer Offline OP
Serious User
Redeemer  Offline OP
Serious User

Joined: Dec 2008
Posts: 1,660
North America
Hello again laugh

The pathfinding solution presented by Damocles has been coming along very well. My units know how to navigate the graph in eight directions, so a unit can move north/south/west/east and diagonally. They can also find their way around simple obstacles like pits and mountains, since I am taking terrain into account when the graph is built.

But I have encountered a problem in my graph building method. The units can easily lead themselves into corners and pockets in the terrain from which they cannot leave unless the player manually directs them out. This happens because when the terrain is added to the graph, high-cost graph cells are placed next to low-cost graph cells, creating a "trap" which any unit can fall into.

So what I need to do is "smooth out" the graph, averaging high-cost cells with low-cost cells so that the units can "roll around" these traps without being manually directed to do so. But I don't know of any algorithms that can do this.

So what algorithms would you guys suggest to accomplish this?


Eats commas for breakfast.

Play Barony: Cursed Edition!
Re: RTS Project [Re: Redeemer] #352375
01/03/11 11:40
01/03/11 11:40
Joined: Dec 2008
Posts: 1,218
Germany
Rackscha Offline
Serious User
Rackscha  Offline
Serious User

Joined: Dec 2008
Posts: 1,218
Germany
I dont understand the problem: If theres is no place in thise bags to get out (for example to arrive the goal point) the Pathdinding should raise the used cost as high as needed to get to the point. At fist in searches for the lowest cost, but if theres no way, it uses the next higher costs etc. Am a bit surprised that your units hang there. Shouldnt happen with a normal a* or djikstra o.O


MY Website with news of my projects:
(for example my current
Muliplayer Bomberman,
GenesisPrecompiler for LiteC
and TileMaster, an easy to use Tile editor)
Sparetime-Development

Re: RTS Project [Re: Rackscha] #352379
01/03/11 11:51
01/03/11 11:51
Joined: Feb 2009
Posts: 2,154
Damocles_ Offline
Expert
Damocles_  Offline
Expert

Joined: Feb 2009
Posts: 2,154
When you build the graph correctly, this should not happen.

before the "floodfill" initialize every grid with a very high number. (20000 for example)
The targetpoint has the lowest number (0 for example)

After the floodfill, every gridpoint must then have a neighbor with at least one "lower" count than itself.
If the graph is build correcly you cant get stuck (not finding
a lower neighbor) unless you already reached the target, or
you are on an impassable grid (wich should not be a valid action).
Or if you are on an isolated island. (indicated by you grid
beeing "20000")

Best is if you make a visualization routine, to show
the assigned number of each grid suqare (or a colorvalue)
So you can manually check if the graph is build correctly.

Also: when creating the grid, make the cost of moving diagonally
1.41 times the cost of moving left or right.
(1.4142 -> sqrt(2) )

Re: RTS Project [Re: Damocles_] #352435
01/03/11 17:27
01/03/11 17:27
Joined: Dec 2008
Posts: 1,660
North America
Redeemer Offline OP
Serious User
Redeemer  Offline OP
Serious User

Joined: Dec 2008
Posts: 1,660
North America
Quote:
Am a bit surprised that your units hang there. Shouldnt happen with a normal a* or djikstra o.O

I'm not using A* or Djikstra. wink

I had my doubts you would understand what I am saying, so I created some pictures showing in stages what I do to generate the graph. The highest points are white, and the low points are black (just so we're clear).

Stage 1: The graph is empty. The cost of every cell is zero.


Stage 2: Cells farther from the destination are raised by either their horizontal or vertical distance, whichever is larger. Thus a diamond shaped "bowl" is formed, with the destination at the lowest point:


Stage 3: Terrain is added to the path. Walkable areas aren't added, only obstacles like mountains, pits, etc.


But obviously problems can arise in scenarios like this:

(The green dot is the start point, the red dot is the destination)

Naturally the green dot travels to the northwest as it is the path of least resistance, but the dot will inevitably get caught between the mountain and the terrain around it like a marble.

To fix this without ever having to make the mountains passable, I devised a solution wherein these "pockets" are smoothed out and/or filled in so that the green dot simply "rolls" around them, like this:


I'm pretty sure there are algorithms available that I can use to achieve this, but I'm not sure what they are. So what I was asking in my original post was, "What algorithm would you guys suggest for this?" wink

Quote:
Also: when creating the grid, make the cost of moving diagonally
1.41 times the cost of moving left or right.
(1.4142 -> sqrt(2) )

Excuse my objection/misunderstanding, but why would I want to do this? Isn't it less costly to travel diagonally then in a straight direction? After all, the length of the hypotenuse of a triangle is always less than the sum of the lengths of the other two sides.

EDIT: It doesn't matter if the smoothing algorithm is slow, I can precompute the smoothed "terrain-graph" and overlay it on top of the real pathfinding graph when the graph is being built.


Eats commas for breakfast.

Play Barony: Cursed Edition!
Re: RTS Project [Re: Redeemer] #352537
01/04/11 10:56
01/04/11 10:56
Joined: Feb 2009
Posts: 2,154
Damocles_ Offline
Expert
Damocles_  Offline
Expert

Joined: Feb 2009
Posts: 2,154
Ok, you did not actually implement it the way i ment it:

The terrain is not "added" on a later stage, but integral
part of the floodfill search.

Here the actual source of the floodfill i used in Java:
It should be easy to follow when you know C :

Code:
static final int pdimX=120;
    static final int pdimY=60;
    
    final int[][] terrainGrid = new int[STUCTURE_FIELD_SIZEX][STUCTURE_FIELD_SIZEY];

    final int gridFlood[][][]=new int[60][pdimX][pdimY];
    final int floodCurrentID=0; //gets counted up for each new floodfill
    
    //if target is on inaccebible floor, create a curcular floodfill, so units can walk towards it
    
    void floodfill (int targetX,int targetY, int gridId)
    {
    //set the targetzone
    int x=targetX;
    int y=targetY;
    
    //make the floodfillgrid
    //Logger.out("steps:"+generateGrid());
    
    int testvalue=0;  //remove!
    //check if target is on a valid square?

    //create the basegrid
    
    // grid = new int[pdimX][pdimY];
    
    //reset all squares to high count (system copy array faster)
    //System.arraycopy(gridInit, 0, grid, 0, gridInit.length);
    
    for (int ix=0;ix<pdimX;ix++)
    {
        for (int iy=0;iy<pdimY;iy++)
        {
        //grid[ix][iy]=gridInit[ix][iy]; //set to a high value
        gridFlood[gridId][ix][iy]=8192;//set to a high value
        } 
    }
    
    //checkif target is on inaccebile position, do a "no matter what" floodfill,
    //so units can walk toward the destination
    
    boolean dontCareForObstacles=false;
    if(terrainGrid[targetX][targetY]==0) dontCareForObstacles=true;
    
    
    //create the list of currently used squares
    //int worklist[][]=new int[dimX*dimY][2];  //trying a lower dimension reduces the memory use..
    int worklistLenght=0;
    
    //int nextlist[][]=new int[dimX*dimY][2];  //trying a lower dimension reduces the memory use..
    int nextlistLenght=0;
   
    //workarrays
    worklist=new int[pdimX*pdimY][2];
    
       // Logger.out("worklist lenght:"+worklist.length);
        nextlist=new int[pdimX*pdimY][2];
        
    //set the targetpoint to 0
    
    gridFlood[gridId][x][y]=0; //the targetsqare start with the lowest count
    
    //targetnode is the first entry
    worklist[1][0]=x;
    worklist[1][1]=y;
    worklistLenght=1;
    
    
     int testsquare=0;
     int xTemp=0;
     int yTemp=0;
     int xNow=0;
     int yNow=0;
     int countThrough=0;
     
     boolean diagonal=false;
     int walkdist=10; //10 for normal, 14 for diagonal
     
     
     //TODO:
     //when the target is on a building, make this building invisible, right now
     //the trick is to have a little gap in 3x3 buildings, wich is just a workaround
     
    
    //as long as squares active:
    while(worklistLenght>0)
    {
        
        countThrough=1; //start with the first entry
        nextlistLenght=0; //"erase" the nextlist
        
        //for all in the worklist
        while(countThrough<=worklistLenght)
        {
        
        testsquare=0;
        //get the nodes position
        xNow=worklist[countThrough][0];
        yNow=worklist[countThrough][1];
        
        
        
        
        while(testsquare<8)
        {
        testvalue++;//erase
        
        //make that smaller
        //select a neighbor square
        
        xTemp=0;yTemp = 0;
        
        diagonal=false;
        
        //smaller classfile than switch..
        if(testsquare==0) {xTemp = 1;}
        if(testsquare==1) {xTemp = 1;yTemp = 1;diagonal=true;}
        if(testsquare==2) {yTemp = 1;}
        if(testsquare==3) {xTemp = -1;yTemp = 1;diagonal=true;}
        if(testsquare==4) {xTemp = -1;}
        if(testsquare==5) {xTemp = -1;yTemp = -1;diagonal=true;}
        if(testsquare==6) {yTemp = -1;}
        if(testsquare==7) {xTemp = 1;yTemp = -1;diagonal=true;}
        
        
        xTemp=xNow+xTemp;
        yTemp=yNow+yTemp;
        

        //check if neighbor is in valid range
        if((xTemp>-1)&&(xTemp<pdimX)&&(yTemp>-1)&&(yTemp<pdimY))
        {
            //is it a passable tile? (also checking for the buildingblockings)
         // if(basegrid.LayerPathfindingMain[xTemp][yTemp]==0)
            
            if(terrainGrid[xTemp][yTemp]==1 || dontCareForObstacles) //1-> means ist passable here ///could check for Buildingsquares here too
            {
              
            //each square finding a valid neightbor with acount higher then this squares count+1 -> set to thiscount+1 and add to next list
      
             // Logger.out("nextlistLenght:"+nextlistLenght+"   x:"+xNow+"   y:"+yNow+"grid:"+grid[xNow][yNow]+" other:"+grid[xTemp][yTemp]);
            
                //this takes into account that diagonal movement costs more
            walkdist=10;
            if(diagonal) walkdist=14;
                   
            if(gridFlood[gridId][xTemp][yTemp]>(gridFlood[gridId][xNow][yNow]+walkdist))  //neighbor has bigger stepcount than me?
            {
            //mark the neightbor
            gridFlood[gridId][xTemp][yTemp]=(short)(gridFlood[gridId][xNow][yNow]+walkdist);  //set the stepcount to my stepcount plus one
            //TODO: should be a different value for diagonal movement!, to make paths smoother
            
            
            //grid[xTemp][yTemp]+=basegrid.LayerBuildingblocking[xTemp][yTemp]*3; //this can be used to make building "half passable"
            
            //add this neighbor for the next check
            nextlistLenght++;
            nextlist[nextlistLenght][0]=(short)xTemp;
            nextlist[nextlistLenght][1]=(short)yTemp;
            }
              
          }
        }
        
        //choose the next possible neighbor
        testsquare++;
        }
        //test the next node in the worklist
        countThrough++;
    }
    
    //copy the nextlists contents to the current worklist
     //System.arraycopy(nextlist, 0, worklist, 0,nextlistLenght*2); 
 
        worklistLenght=nextlistLenght;
    
        for (int ix=0;ix<=nextlistLenght;ix++)
        {
            worklist[ix][0]=nextlist[ix][0];
            worklist[ix][1]=nextlist[ix][1];
            
        }
     
     
     
    }
    
    
    
    }
 
    
    //create the list of currently used squares
    static int worklist[][]=null;  //trying a lower dimension reduces the memory use..
    static int nextlist[][]=null;  //trying a lower dimension reduces the memory use..



Last edited by Damocles_; 01/04/11 10:57.
Re: RTS Project [Re: Redeemer] #352543
01/04/11 11:45
01/04/11 11:45
Joined: Oct 2009
Posts: 149
Germany
M
muffel Offline
Member
muffel  Offline
Member
M

Joined: Oct 2009
Posts: 149
Germany
Why do you not use a normal floodfill algortihm which is able to change the value which is drawn
WIKI

EDIT: I should actualize the browser window more often

muffel

Last edited by muffel; 01/04/11 11:47.
Re: RTS Project [Re: muffel] #352565
01/04/11 13:56
01/04/11 13:56
Joined: Dec 2008
Posts: 1,218
Germany
Rackscha Offline
Serious User
Rackscha  Offline
Serious User

Joined: Dec 2008
Posts: 1,218
Germany
@Redeemer but if you use A* or Djikstra, they wouldnt hang there wink
You wouldnt have to "patch" the graph.


MY Website with news of my projects:
(for example my current
Muliplayer Bomberman,
GenesisPrecompiler for LiteC
and TileMaster, an easy to use Tile editor)
Sparetime-Development

Re: RTS Project [Re: Rackscha] #352608
01/04/11 18:57
01/04/11 18:57
Joined: Dec 2008
Posts: 1,660
North America
Redeemer Offline OP
Serious User
Redeemer  Offline OP
Serious User

Joined: Dec 2008
Posts: 1,660
North America
Oh. I understand what I'm supposed to be doing now.

Quote:
Why do you not use a normal floodfill algortihm which is able to change the value which is drawn

That was my problem. I totally misunderstood how I was supposed to generate the graph.

Quote:
but if you use A* or Djikstra, they wouldnt hang there

They also wouldn't hang there if I used the floodfill algorithm properly. tongue

This shouldn't be hard to fix now that I know what I'm doing. Thanks for the input guys. laugh


Eats commas for breakfast.

Play Barony: Cursed Edition!
Page 4 of 4 1 2 3 4

Gamestudio download | chip programmers | Zorro platform | shop | Data Protection Policy

oP group Germany GmbH | Birkenstr. 25-27 | 63549 Ronneburg / Germany | info (at) opgroup.de

Powered by UBB.threads™ PHP Forum Software 7.7.1