Sign in to follow this  
BaneTrapper

c++, Help up with algoritham and/or math

Recommended Posts

Hello.

Currently i am trying to figure out how i am gonna calculate vision range of my units in 2d tile based map.

 

The issue is my map goes up to 100x100 in size, and i need access of variable in one of tiles for AI logic.

 

For example:

o = player;

x = sight range

n = tile out of sight range

 

In case x = 1

Amount of tiles in sight = 4

n n n n n

n n x n n

n x o x n

n n x n n

n n n n n

 

In case x = 2

Amount of tiles in sight = 12

n n x n n

n x x x n

x x o x x

n x x x n

n n x n n

 

In case x = 3

Amount of tiles in sight = 24

n n n x n n n

n n x x x n n

n x x x x x n

x x x o x x x

n x x x x x n

n n x x x n n

n n n x n n n

 

 

What do i do for calculation?

I need to loop each tile and check its type, i also need to figure out the tile that is closest,

How would i access the tiles from a vector that are filed like this?

I have a position in vector, and sight range.

vector<Tile> tileList; //10x10 map vector array...
int unitsVecPos = 25;//units position in vector array
int sightRange = 3;//range of tiles unit can see from its origin
 
//Check if there is a grass tile in the sight range of unit

Questions:

1: How to calculate amount of tiles i need to loop in case of x sight range?

2: Any idea on algorithm for accessing the tiles when looping for sight range?

 

Example:

for(int i = 0; i < amountOfTilesToLoop; i++)
{
    if(tileList[tileIDStart + i].type == GrassType)//I the tileIDStart + i is totally wrong but :(
    {
        if(ThisTileIsCloserThenLastMatchingTile == true)
            //Tell AI there is food here
    }
}
Edited by BaneTrapper

Share this post


Link to post
Share on other sites

If you are not concerned about visibility, the fastest method to determine which cells are within a certain radius of another cell is to use the [url="http://en.wikipedia.org/wiki/Midpoint_circle_algorithm"]midpoint circle algorithm[/url].

Share this post


Link to post
Share on other sites

My initial thoughts:

 

Since you're on a grid you can immediately reduce your checks by getting only the tiles that are within position +/- sight in (x,y).  Have a function that returns the set of tiles in this subgrid.

 

In this subgrid do a collision detection with a circle against each of the 4 points of the tile's boundary.   Or if you're only using the center point then c1.  Given, at least one of these points must have a distance to position that is <= to sight.  Make this into a function that inputs the tiles from the previous step and returns an even further culled set.

Share this post


Link to post
Share on other sites

it appears your storing a 2d world map as a 1d array (list) of map squares (tiles). in that case, your difficulty comes from storing the data in  a structure other than the manner that the data naturally occurs. the natural structure of a 2d tile based map is a 2d array, not a 1d array list of tiles. 

 

once you switch from a  tile_list[100] to a map[10][10], everything becomes easy.

 

 

player is at x,y (IE map[x][y]).

 

visual range =2;

 

the area of tiles to loop through is :

 

for (x0= x-2, x0 <=x+2, x0++)

for (y0= y-2, y0 <=y+2, y0++)

      // process tile x,y

 

for the closest tile of a given type, its the old "find the best" search algo:

 

best_dist=some very large value (like 100 tiles away on a map thats only 10x10)

best_tile=none

for each tile to check (a double for loop in x0 and y0):

    if tile isn't the type we want, continue.

    if  dist2player < best_dist: 

         best_dest= dist2player,

         best_tile = x0,y0

return best_tile, best dist, or both.

 

 

dist2player < best_dist returns the first matching tile found at whatever the closest distance is.

dist2player <= best_dist returns the last matching tile found at whatever the closest distance is.

 

 

dist2player can just be bounding box distance from x1,y1 to x2,y2:

 

return lesser of: (x2-x2) or (y2-y1).

 

or true Euclidean 2d distance:

 

dist= sqrt (  (x2-x1) * (x2-x1) + (y2-y1) * (y2-y1)  )  

Edited by Norman Barrows

Share this post


Link to post
Share on other sites


1: How to calculate amount of tiles i need to loop in case of x sight range?
2: Any idea on algorithm for accessing the tiles when looping for sight range?

 

the number of tiles to check will be (vis_rng * 2 + 1 ) ^ 2.  ie: vis_rng=3, number of tiles to check = 2*3=6. 6+1=7. 7*7=49 titles. 

 

if you want to use a 1d array, you just address it like a bitmap. array index = y*map_width+x.  then you do the usual 2d array stuff, and convert to a 1d array index for lookups from your tile list.

 

but a 2d array is a cleaner implementation.

Share this post


Link to post
Share on other sites

I am thankful for such list of replies.

I gave it a hour, still no clear knowledge how to get this done.

For now i will hardcore the code until i get more interest intro getting a algorithm.

 

EDIT::
I got the idea how to loop and check if the X is in sight range, but i got no idea how to check only tiles that are in sight range because if i loop all the tiles are they in sight range its not gonna be fast.

 

EDIT2:
I just figured out a simple solution (Sight range to amount of tiles)

int total = 0;
for(int i = 0 i < sightRange; i++)
{
total += sightRange - i;
}
total = total * 4;
 

That is amount of tiles.
I also figured out that i just wasted my time on something i don't actually need :D.
I need to figure out witch tiles i need to check from 1d array...

Edited by BaneTrapper

Share this post


Link to post
Share on other sites

If you are not concerned about visibility, the fastest method to determine which cells are within a certain radius of another cell is to use the midpoint circle algorithm.

Would anyone be willing to post a simple example using "midpoint circle algorithm." i just cant figure it out.

 

EDIT:: I am also gonna use this to make a highligh/(How much does he see), so it shows how long, or much can a player can see.

In other words, a highlight is gonna be drawn on each tile that fits this algoritham on his "Sight Range"

 

Trying to make AAA title AI.
Report day 1:
This will be so cool! i am so gonna get this done.

Report day 2:
Well this seams pretty complicated.

Report day 3:

Frustration, pain, HOW?.

Report day 4:

I am writing this to say, i quit!

Edited by BaneTrapper

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this