• Create Account

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

Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

8 replies to this topic

### #1BaneTrapper  Members   -  Reputation: 826

Like
0Likes
Like

Posted 22 August 2013 - 01:02 PM

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, 22 August 2013 - 01:07 PM.

Current projects:
The Wanderer, 2d turn based rpg style game

www.gamedev.net/topic/641117-check-up-the-wanderer/

### #2Álvaro  Crossbones+   -  Reputation: 8043

Like
1Likes
Like

Posted 22 August 2013 - 01:17 PM

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.

### #3Cosmic314  Members   -  Reputation: 917

Like
0Likes
Like

Posted 22 August 2013 - 01:24 PM

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.

### #4CulDeVu  Members   -  Reputation: 273

Like
0Likes
Like

Posted 22 August 2013 - 04:12 PM

Since your sight range is a diamond in your ASCII art, you could just use a simple Manhattan Distance check:
http://heuristicswiki.wikispaces.com/Manhattan+Distance
I'm sorry about any spelling or grammar mistakes or any undue brevity, as I'm most likely typing on my phone

### #5Norman Barrows  Crossbones+   -  Reputation: 1387

Like
0Likes
Like

Posted 22 August 2013 - 07:45 PM

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, 22 August 2013 - 07:58 PM.

"DirectX is like a belt fed machine gun, where every texture change is like hand loading in a new belt of ammo. worse, every mesh (vb) is a new belt of ammo, and a texture is like breaking the gun down, and setting it up again elsewhere, then loading it, then spraying triangles again. so you want to setup the gun once, string all your belts together, load it once, then just spray."

Norm Barrows
Rockland Software Productions
"Building PC games since 1988"

### #6Norman Barrows  Crossbones+   -  Reputation: 1387

Like
0Likes
Like

Posted 22 August 2013 - 07:54 PM

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.

"DirectX is like a belt fed machine gun, where every texture change is like hand loading in a new belt of ammo. worse, every mesh (vb) is a new belt of ammo, and a texture is like breaking the gun down, and setting it up again elsewhere, then loading it, then spraying triangles again. so you want to setup the gun once, string all your belts together, load it once, then just spray."

Norm Barrows
Rockland Software Productions
"Building PC games since 1988"

### #7BaneTrapper  Members   -  Reputation: 826

Like
0Likes
Like

Posted 23 August 2013 - 06:02 AM

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 .
I need to figure out witch tiles i need to check from 1d array...

Edited by BaneTrapper, 23 August 2013 - 06:40 AM.

Current projects:
The Wanderer, 2d turn based rpg style game

www.gamedev.net/topic/641117-check-up-the-wanderer/

### #8Paradigm Shifter  Crossbones+   -  Reputation: 3995

Like
1Likes
Like

Posted 23 August 2013 - 07:48 AM

The number of tiles for sight range N is

2 * (N * (N+1))

"Most people think, great God will come from the sky, take away everything, and make everybody feel high" - Bob Marley

### #9BaneTrapper  Members   -  Reputation: 826

Like
0Likes
Like

Posted 25 August 2013 - 01:00 AM

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, 25 August 2013 - 02:00 AM.

Current projects:
The Wanderer, 2d turn based rpg style game

www.gamedev.net/topic/641117-check-up-the-wanderer/

Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

PARTNERS