|
Re: RTS Project
[Re: Redeemer]
#352236
01/02/11 12:10
01/02/11 12:10
|
Joined: Nov 2002
Posts: 913 Berlin, Germany
SchokoKeks
User
|
User
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:
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: Redeemer]
#352355
01/03/11 04:07
01/03/11 04:07
|
Joined: Dec 2008
Posts: 1,660 North America
Redeemer
OP
Serious User
|
OP
Serious User
Joined: Dec 2008
Posts: 1,660
North America
|
Hello again 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?
|
|
|
Re: RTS Project
[Re: Redeemer]
#352375
01/03/11 11:40
01/03/11 11:40
|
Joined: Dec 2008
Posts: 1,218 Germany
Rackscha
Serious User
|
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: Damocles_]
#352435
01/03/11 17:27
01/03/11 17:27
|
Joined: Dec 2008
Posts: 1,660 North America
Redeemer
OP
Serious User
|
OP
Serious User
Joined: Dec 2008
Posts: 1,660
North America
|
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. 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?" 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.
|
|
|
Re: RTS Project
[Re: Redeemer]
#352537
01/04/11 10:56
01/04/11 10:56
|
Joined: Feb 2009
Posts: 2,154
Damocles_
Expert
|
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 :
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
muffel
Member
|
Member
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
Serious User
|
Serious User
Joined: Dec 2008
Posts: 1,218
Germany
|
@Redeemer but if you use A* or Djikstra, they wouldnt hang there 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
OP
Serious User
|
OP
Serious User
Joined: Dec 2008
Posts: 1,660
North America
|
Oh. I understand what I'm supposed to be doing now. 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. but if you use A* or Djikstra, they wouldnt hang there They also wouldn't hang there if I used the floodfill algorithm properly. This shouldn't be hard to fix now that I know what I'm doing. Thanks for the input guys.
|
|
|
|