Public Group

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

This topic is 2151 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## 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 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.

##### 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 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 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 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 on other sites

The number of tiles for sight range N is

2 * (N * (N+1))

##### 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

• 9
• 17
• 10
• 11
• 18