Easy way to find if a point is accessible by unit X?

krogothe · Post by **krogothe** » 06 Mar 2006, 16:37

Ive given up trying to use the spring pathfinder, it wont suit my needs unfortunately! So im writing my own, but to make it work i need a way to tell if a certain unit can pass through a certain point on the map (based on slope and the units maxslope). How is this done?

Weaver · Post by **Weaver** » 06 Mar 2006, 18:56

I'll tell you what I remember

The slope map is generated from the height map, using only alternate points. ie 0,0 0,2 2,0 2,2 etc.

Each point is compared against its neigbours, so 2,2 would be checked against 0,0 0,4 4,0 4,4

The maximum difference determines the slope value and combined with maxslope determines colour seen with a unit selected and F2. For 2,2 the tile would have corners 1,1 1,3 3,1 3,3.

This all results in a fairly poor resolution slope map, something I exploited when making Ashap Plateau, my little spikes are invisible to the slope map and have no slope cost as they are not placed on sampled points.

Buildsite slope is calculated differently using all height points, the reason for the spikes in Ashap Plateau was to reduce the usable build area in the lower region.

krogothe · Post by **krogothe** » 06 Mar 2006, 19:25

So the accessibility map is the same res as the metalmap res?
and by maximum difference do you mean the highest out of ALL adjacent points?
Are adjacent points just the corners or the ones directly above,below and at its sides?
Lastly, any general values for kbot/vehicle maxslopes?

Ill be using a a* approach, and with the acessbility map i should be ready to go!
Thanks a lot!

AF · Post by AF » 06 Mar 2006, 19:50

Ah krogothe, could you make such code public? I'm in dire need of a blocking map for a decent building algorithm I have in mind, but I'm going to have to go down the same route as you if I cant get the blocking map in spring tied into the interface.

Weaver · Post by **Weaver** » 06 Mar 2006, 20:44

So the accessibility map is the same res as the metalmap res?
Need to check my notes I will answer later
Yes, but due to way it samples it is effectively less

and by maximum difference do you mean the highest out of ALL adjacent points?
Are adjacent points just the corners or the ones directly above,below and at its sides?
Corners and centre, the largest difference to centre point in altitude higher or lower is used.I am not so sure now, I think it may compare corner heights to each other.

If that seems a little odd, it is. The final slopemap res is effectively a quarter the res of the heightmap. I am sure it could be improved by using better sampling points with no increase in filesize or overhead.

krogothe · Post by **krogothe** » 06 Mar 2006, 21:18

Cool! I also need to know how a unit's speed is affected by slope etc, so i guess ill have to read lots of spring code! Would be great if a dev came here and explained it all though

Post by SJ » 07 Mar 2006, 08:26

Weaver, the point of the slope map is to be a bit fuzzy, in the earliest version I used an algorithm where we got a more exact fit but it didnt look good when a big unit couldnt traverse a very small bump so instead I changed to the current somewhat lowpass filtered version.

Weaver · Post by **Weaver** » 07 Mar 2006, 10:21

SJ wrote:Weaver, the point of the slope map is to be a bit fuzzy, in the earliest version I used an algorithm where we got a more exact fit but it didnt look good when a big unit couldnt traverse a very small bump so instead I changed to the current somewhat lowpass filtered version.

Ok that makes sense, and is pretty efficient way of doing it.

AF · Post by AF » 07 Mar 2006, 20:47

Coudlnt you take the currnt pathfinder, get allthe waypoints between unitpos and the target location adn check how far the final waypoint is from the destination? Then you can use that difference as a gauge of wetehr you can get there or not. Or you can sue that combined with the pathweight(if the pathweight call has been uncommented from 0.67b3 that is)

krogothe · Post by **krogothe** » 07 Mar 2006, 20:54

I would if it would actually explain how to change the movetype of the theoretical unit, its no use getting points over water and impassable mountains

AF · Post by AF » 07 Mar 2006, 21:00

hmm is ti passing a UnitDef? I alwas found I could fiddle those functions by making my own untiDef and passing that instead...

krogothe · Post by **krogothe** » 07 Mar 2006, 21:03

Code: Select all

	//the following functions allows the dll to use the built in pathfinder
	//call InitPath and you get a pathid back
	//use this to call GetNextWaypoint to get subsequent waypoints, the waypoints are centered on 8*8 squares
	//note that the pathfinder calculates the waypoints as needed so dont retrieve them until they are needed
	//the waypoints x and z coordinate is returned in x and z while y is used for error codes
	//>=0 =worked ok,-2=still thinking call again,-1= end of path reached or invalid path
	virtual int InitPath(float3 start,float3 end,int pathType) = 0;
	virtual float3 GetNextWaypoint(int pathid) = 0;
	virtual void FreePath(int pathid) = 0;

	//This function returns the approximate path cost between two points(note that it needs to calculate the complete path so its somewhat expansive)
	virtual float GetPathLength(float3 start,float3 end,int pathType)=0;

where do i stick that unitdef? Do i not get this whole pathfinder callback thing or have you never even tried using it?

AF · Post by AF » 07 Mar 2006, 21:07

Oh, it's just i havent used it in a long while nro ahs anyone else.. I believe there's an explanation fot he 4 values you need for that path type itneger, look through the files defining MoveData and the handlers and loaders for it it'll be there....

krogothe · Post by **krogothe** » 07 Mar 2006, 21:09

yeah i had a look, still got valid paths for ships/kbots etc everywhere

Chocapic · Post by **Chocapic** » 07 Mar 2006, 22:08

funny cause as i saw you showing up that function it reminded me what i had seen for a large bunch of versions, wich is this :

Code: Select all

float CAICallback::GetPathLength(float3 start,float3 end,int pathType)
{
//	return pathfinder->GetPathLength(start,end,pathType);
	return 0;
}

krogothe · Post by **krogothe** » 14 Mar 2006, 21:44

I did what weaver told me, with a few changes, it renders in miliseconds and looks fairly accurate, so i guess ill use it for my first experiments.
Tell me if those pictures look okay:

Should be pretty straightforward to guess which is which, althogh the second one shows the need for tweaking on the side, where i just assumed the map carries on due to lazyness!

EDIT:
Fixed metalheck:

As a sidenote, KAI is now at 5.5k lines in 39 files, making it the second biggest AI (that ive seen the source of, behind OTAI with almost 8k), with roughly 1k of stuff still to be rewritten and about 5k more still to be done! Im starting the really cool work ive always planned but was never able to do, and it should be worthy of another test release before the finished thing (again with placeholder economy systems) in a couple of weeks! Keep tuned!

Weaver · Post by **Weaver** » 14 Mar 2006, 23:35

This the top left of Ashap Plateau, note edges of all maps are voided and the spires on this map dodge the heightmap samples.

If your filter give the same result you are very close.

krogothe · Post by **krogothe** » 15 Mar 2006, 00:13

Weaver, thats awesome, just what i needed! I should be able to get a real slopemap comparing with that screen (no it still gives high slopes due to the higher res used). Thank you loads!

AF · Post by AF » 15 Mar 2006, 20:23

Krogothe would you midn releasing source for this 'experiment' I have dire need for something like this and I'd prefer not to stretch my already limited resources even further trying to recreate what you've done.

A line count of NTAI 0.28 once took me to the 6.4k line region. But I dont have a line counting program atm so I cant test the XE7.5 build for you...

krogothe · Post by **krogothe** » 15 Mar 2006, 20:54

I counted it for you. NTAI XE has about 4.6k lines (of real code) in the version bundled with spring...
I wont be releasing anything until its done, and really, it took me 2 mins to write the code to get the slopemap. You could write it faster than it takes you to make a post, and you post like mad.
EDIT:
just have it tbh, its slow and dirty (and its not yet accurate), but if you cant be arsed doing it yourself, no harm done in using mine:

Code: Select all

	for(int i = 0; i < totalcells; i++)	{
		float maxslope = 0;
		float tempslope;
		if(i+1 < totalcells && (i + 1) % PathMapXSize){	
			tempslope = abs(HeightMap[i] - HeightMap[i+1]);
			if(tempslope > maxslope)
				maxslope = tempslope;
		}
		if(i - 1 >= 0 && i % PathMapXSize){
			tempslope = abs(HeightMap[i] - HeightMap[i-1]);
			if(tempslope > maxslope)
				maxslope = tempslope;
		}
		if(i+PathMapXSize < totalcells){
			tempslope = abs(HeightMap[i] - HeightMap[i+PathMapXSize]);
			if(tempslope > maxslope)
				maxslope = tempslope;
		}
		if(i-PathMapXSize >= 0){
			tempslope = abs(HeightMap[i] - HeightMap[i-PathMapXSize]);
			if(tempslope > maxslope)
				maxslope = tempslope;
		}

}

For now, you can have a sneak preview

I need to pull a 10x performance increase out of it if i want it to work as desidered, but its a promising start!

Spring RTS Engine

Easy way to find if a point is accessible by unit X?

Easy way to find if a point is accessible by unit X?