12 replies to this topic

[VidiVici]

I've separated this topic from the Learning AI topic as they are separate things

My ThreatOnPath code using a pie-segment <) to find if an enemy poses a thread rather than a band =

-- Arkhan 03.2006: Work around for Relics buggy HasThreatOnPath() function-- VidiVici 10.2007: Changed to check a cone and potential cover from friendly unitfunction CpuManager:HasThreatOnPath(startPos, targetPos, iRange)	dbAssert(startPos ~= nil)	dbAssert(targetPos ~= nil)	dbAssert(iRange ~= nil)			-- Check if high speed AI setting is activated	if (CpuManager.AISettings.bHighSpeedAI == true) then		return false	end	-- Update object table	if (g_iGMT > self.m_iLastTableUpdate + 5) then		self:UpdateObjectTable()		self.m_iLastTableUpdate = g_iGMT	end	-- polar coordinates of target	local rTarget = self:DistanceXZ(startPos, targetPos)	local tTarget = self:AngleXZ(startPos, targetPos)	-- if rTarget > iRange then look for danger in cone	if (rTarget > iRange) then		-- define dangerCone angle		local angle = math.atan2( iRange, rTarget )		-- dangerCone bounderies		local rRad = rTarget + iRange		local mint = tTarget - angle		local maxt = tTarget + angle		-- Check for threat		local threatDist		local threatAngle		for iLoop1 in self.m_aThreatPositions do			-- Get threat position			threatPos = self.m_aThreatPositions[iLoop1]			-- polar coordinates of threat			threatDist 	= self:DistanceXZ(startPos, threatPos) 			threatAngle = self:AngleXZ(startPos, threatPos)			-- check if threat is in dangerCone			if (threatDist < rRad and threatAngle > mint and threatAngle < maxt ) then				print("DANGER @ ["..threatPos.x..", "..threatPos.z.."]"..				" Form ["..startPos.x..", ".. startPos.z .."]"..				" to [".. targetPos.x ..", ".. targetPos.z .."]".." ("..iRange..")")				-- check if threat cen be countered				if (not self:FriendInRange(threatPos, iRange)) then					return true				end			end		end	else -- rTarget <= iRange check threat proximity to target	   for iLoop1 in self.m_aThreatPositions do			-- Get threat position			threatPos = self.m_aThreatPositions[iLoop1]			-- distance of threat to target			threatDist 	=  self:DistanceXZ(targetPos, threatPos)			-- check if threat is in dangerCone			if ( threatDist < iRange ) then				print("DANGER @ ["..threatPos.x..", "..threatPos.z.."] around [".. targetPos.x ..", ".. targetPos.z .."]")				if (not self:FriendInRange(threatPos, iRange)) then					return true				end			end		end	end	return falseend-- VidiVici 10.2007: computes the distance between 2 points-- WARNING! no nil check for positions use with carefunction CpuManager:DistanceXZ(pos1, pos2)    local tmp = Vector3f (0,0,0)	tmp.x = pos2.x - pos1.x	tmp.z = pos2.z - pos1.z	return math.sqrt(tmp.x*tmp.x + tmp.z*tmp.z )end-- VidiVici 10.2007: computes the angle between 2 points-- WARNING! no nil check for positions use with carefunction CpuManager:AngleXZ(pos1, pos2)    return math.atan2( pos2.x - pos1.x , pos2.z - pos1.z  )end-- VidiVici 10.2007: checks if a friendly unit is located around a postion-- WARNING! no nil check for position use with carefunction CpuManager:FriendInRange(pos, iRange)	-- Update object table	if (g_iGMT > self.m_iLastTableUpdate + 5) then		self:UpdateObjectTable()		self.m_iLastTableUpdate = g_iGMT	end	for fLoop in self.m_aFriendlyPositions do		-- get friendly postion		fPos = self.m_aFriendlyPositions[fLoop]		-- if friendly can cover there is no threat		if ( self:DistanceXZ(pos, fPos) < iRange ) then		   print("Friendly @ ["..fPos.x..", "..fPos.z.."]")		   return true		end	endend-- Arkhan 06.2006: Inits object tables to increase performance -- VidiVici 07.2007: Added FriendlyPositions tablefunction CpuManager:UpdateObjectTable()	-- Update tables	self.m_aEnemyUnits = {}	self.m_aAlliedUnits = {}	self.m_aMyUnits = {}	self.m_aEnemyTurrets = {}	self.m_aAlliedTurrets = {}	self.m_aMyTurrets = {}	self.m_aThreatPositions = {}	self.m_aFriendlyPositions = {}		for oPlayer in cpu_manager.stats:GetPlayerStats() do			-- Check if player is still alive		if (not oPlayer:IsPlayerDead()) then				-- Check if player is an enemy			local bEnemy = self.player_stats:IsEnemy(oPlayer)						-- Check if player is an ally			local bAlly = (not bEnemy and oPlayer:GetPlayerID() ~= self.player_id)									-- Compute all player units			for oSquad in oPlayer:GetSquads() do										-- Check if unit is valid							if (oSquad:IsValid() and not oSquad:IsEngineer()) then											-- Check squad strength					local iSquadStrength = cpu_manager:GetUnitStrength(oSquad)					if (iSquadStrength > 0) then											-- Add unit to table						if (bEnemy) then							table.insert(self.m_aEnemyUnits, { Vector3f(oSquad:GetPosition()), iSquadStrength })							if (iSquadStrength > 100) then								table.insert(self.m_aThreatPositions, Vector3f(oSquad:GetPosition()))							end						elseif (bAlly) then							table.insert(self.m_aAlliedUnits, { Vector3f(oSquad:GetPosition()), iSquadStrength })							if (iSquadStrength > 100) then								table.insert(self.m_aFriendlyPositions, Vector3f(oSquad:GetPosition()))							end						else							table.insert(self.m_aMyUnits, { Vector3f(oSquad:GetPosition()), iSquadStrength })							if (iSquadStrength > 100) then								table.insert(self.m_aFriendlyPositions, Vector3f(oSquad:GetPosition()))							end						end					end				end			end						-- Compute all player turrets			local sRace = oPlayer:GetPlayerRaceName()			local iPostThreat = self:GetTurretPower(sRace)			for oBuilding in oPlayer:GetBases() do								-- Check for valid building				if (oBuilding:IsValid() and oBuilding:HasGuns()) then									-- Check for posts					if (oBuilding:IsListeningPost()) then												-- Add post to table						if (bEnemy) then							table.insert(self.m_aEnemyTurrets, { Vector3f(oBuilding:GetPosition()), iPostThreat })							table.insert(self.m_aThreatPositions, Vector3f(oBuilding:GetPosition()))						elseif (bAlly) then							table.insert(self.m_aAlliedTurrets, { Vector3f(oBuilding:GetPosition()), iPostThreat })							table.insert(self.m_aFriendlyPositions, Vector3f(oBuilding:GetPosition()))						else							table.insert(self.m_aMyTurrets, { Vector3f(oBuilding:GetPosition()), iPostThreat })							table.insert(self.m_aFriendlyPositions, Vector3f(oBuilding:GetPosition()))						end					else						-- Get building name and threat						local sBuildingName	= oBuilding:GetBaseName()						local sBuildingType, iThreat = self.m_oRaceLoader:GetBuildingType(sRace, sBuildingName)						if (iThreat > 0) then									-- Add turret to table							if (bEnemy) then								table.insert(self.m_aEnemyTurrets, { Vector3f(oBuilding:GetPosition()), iThreat })								table.insert(self.m_aThreatPositions, Vector3f(oBuilding:GetPosition()))							elseif (bAlly) then								table.insert(self.m_aAlliedTurrets, { Vector3f(oBuilding:GetPosition()), iThreat })								table.insert(self.m_aFriendlyPositions, Vector3f(oBuilding:GetPosition()))							else								table.insert(self.m_aMyTurrets, { Vector3f(oBuilding:GetPosition()), iThreat })								table.insert(self.m_aFriendlyPositions, Vector3f(oBuilding:GetPosition()))							end						end					end				end			end		end	endend

What do you think of it?

On another note I need some help to fully test it. What map is prone to misdirect the builders?

The next steps will be to
1) Cancel thread when a friendly unit is near the potential threat to avoid being boxed in by a unit who will not be able to effectively harm the builder. DONE
2) Locate impassable terrain and adapt the DangerCone to have bends in it...

The builders seem to wait a long time b4 moving to go build LP's can't they move in a bit faster to avoid having to span big distances?
Is there command to make the AI ping on the minimap? It would be a lot easier to see what points/units are involved,
and I have added the friendly unit check.

ThreatMap
More complex systems to try and find the safest path to a point will be quite heavy imo as I think it will require:
1) Having a threatMap mapping potential threat in each point.
2) Defining impassable zones by combining impassable terrain and all zones above a certain threshold.
3) Performing an heuristic search similar to A-star to find the best path.
4) Reducing the path to a couple of target points that have to be followed and updated as battle progresses.

Edited by VidiVici, 02 October 2007 - 02:31 PM.

[thudo]

VidVici - EXCELLENT WORK! I do have a map this can be tested and will do that tonight. One that is a 1vs1 but has winding hills and challenging choke points. This can easily and quickly be tested using AI vs AI battles on HARD skill at an INSANE game speed to overview the behaviour. Well done!

[ArkhanTheBlack]

Oh my, VidiVici, don't get yourself into a dead end. If we would need a cone threat zone I would already programmed it like that. The thing we would really need would be the exact path on the map from one point to another. But since we don't have access to terrain data, the only possible way to figure such a thing out would be observe the way of a unit. But this is also a very unreliable way.

The FriendInRange(pos, iRange) function is obsolete since we already have a function which is doing that. We also have a threat map. The problem is the terrain. The best thing you could do to if you want to address the threat problem would be to improve the capture and resource plans to store information if a capture or post building attempt failed because of an enemy threat. Future capture and build attempt would then be delayed.

On a side note, all our algorithms should be speed optimized. In your reworked algorithms, you are calculating a lot of square roots. But it's much faster to just square the value you want to compare the square root with. That's one multiplication compared to a square root calculation. This is especially important if you use those stuffs in loops. You also use a tangens calculation which is another speed breaker.

I still think that you could get the best results for AI learning to store map information. Although the map name can't be figured out, you can create a symbolic map name through the post positions.

Don't try to just improve my pathing algorithms. As long as you don't use new information like terrain data, they will hardly be better.

[VidiVici]

Hmm conflicting reaction.

Arkhan, I am not yet trying to improve your algorithms, I am only trying to implement some tweaks to get familiar with the syntax and the behavior of the AI. You know the "learn to walk before you start running"-issue.

Second, I will not build some impassable terrain learning algorithms or some exotic way to identify maps as this info obviously already present and the addition of a few commands will render most of this work redundant.

Lastly the closest thing I could find to a theatmap is the GetTheatAt function which is not exactly what I am looking for and I would like to know how the map is build before I start using it.

Edited by VidiVici, 02 October 2007 - 11:23 PM.

[ArkhanTheBlack]

Hmm conflicting reaction.

I've implemented the replacement pathing algorithms. I'm not sure if Thudo ever looked at them since this more my area. But Thudo is always (or most often) positive. The big bang comes when the tests results don't work out to his liking . I start to protest as soon as I see something suspicious.

Arkhan, I am not yet trying to improve your algorithms, I am only trying to implement some tweaks to get familiar with the syntax and the behavior of the AI. You know the "learn to walk before you start running"-issue.

Sorry, take your time! I just want to avoid that you waste your and our time by making changes based on wrong assumptions like the terrain information. I also don't understand the change to a cone form.

Second, I will not build some impassable terrain learning algorithms or some exotic way to identify maps as this info obviously already present and the addition of a few commands will render most of this work redundant.

No, neither terrain learning algos nor map identification is present at the moment. I've thought about those ways before, but I considered it as too much work for little gain.

Lastly the closest thing I could find to a theatmap is the GetTheatAt function which is not exactly what I am looking for and I would like to know how the map is build before I start using it.

The object table is pretty much the threat map. It contains info about allied and enemy troops and buildings. This info is updated in intervals of 5 seconds.

[VidiVici]

Hmm I hope it Thudo will not too much of a disappointed

I understand that you don't want to waste your time on bad ideas I should have explained why I chose to implement cones:

1) As the builder will be moving towards the objective it needs to be more concerned by what is near the endpoint then what is currently close to the builder.

2) Cones allow for more mobility as a narrower path is taken in account

3) It is easier to go around an object using cones.
Because you compute the angle between the path and the threat you know what angle you need to rotate to avoid the threat. After that you can get back on track quite easily.
A bit like using a mirror to look behind an object.



Concerning the threatmap I had something different in mind that the tables.
Let me clarify:
The thread posed by a unit is dependent on the damage it does a certain range a Heavy bolter is threatening at range but ineffective in CC. For a Berserker is the opposite.

HB Theat
|..._______............
|_/.............\..........
|__________\_____
Distance

BK Threat
|__........................
|....\____...............
|_______\________
Distance

As these threat profiles differ you can take a path closer to a berserker than to a Heavy Bolter and survive.
The danger posed by the units is thus not a point but a blob with different profiles.

On the theatmap I have in mind the threat blob of all the units are mapped like hightmap.
To avoid threat you can then force the builder to walk in the valleys.

This has the added benefit that a unit can retreat more efficiently as the unit doesn't have to be shot at to realize that it is in danger (personal threat is getting to high)
Ideally this should also be combined with a cover map: increasing the thread of units located in light/heavy cover and reducing that of units in negative cover.

Edited by VidiVici, 03 October 2007 - 01:30 AM.

[troubadour]

On the theatmap I have in mind the threat blob of all the units are mapped like hightmap.
To avoid threat you can then force the builder to walk in the valleys.

But how will you store this information ?
Are you going to use a modified object table with additional columns to describe unit effectivness vs distance ?

I dont know how objects are stored in threatmap but is it possible to store them according to the closer Critical Location or closer Strategic Point so when you want to send a unit to attack a SP you just got to read the info for this point and not to cycle through all objects in the map

Sorry if it has been discussed before or if Arkhan already coded it that way, forgive me if i am out of tracks cause i am not an AI or lua expert

[ArkhanTheBlack]

I understand that you don't want to waste your time on bad ideas I should have explained why I chose to implement cones:

1) As the builder will be moving towards the objective it needs to be more concerned by what is near the endpoint then what is currently close to the builder.

2) Cones allow for more mobility as a narrower path is taken in account

3) It is easier to go around an object using cones.
Because you compute the angle between the path and the threat you know what angle you need to rotate to avoid the threat. After that you can get back on track quite easily.
A bit like using a mirror to look behind an object.

I don't get it. If I want to know if there's a threat between point 1 and point 2, I have to check a constant threat range around the way. If the threat check is to narrow at the start of the path, I'll miss enemy units and turrets and my builder (or other unit) will just be shot down. If the threat check is to wide at the end of the path I'll detect enemy units and turrets which the builder would never face because they are too far away.

Concerning the threatmap I had something different in mind that the tables.

Reminds me of streamline theory. But I don't think it will work because the AI is not fast enough. With 7 AI's it will take 7 seconds until you can control a units movement again.
But well, I guess you will figure out the problems yourself...

I dont know how objects are stored in threatmap but is it possible to store them according to the closer Critical Location or closer Strategic Point so when you want to send a unit to attack a SP you just got to read the info for this point and not to cycle through all objects in the map

Yes, the attack strategy works exactly this way!

[VidiVici]

To store the info I will indeed have to build a matrix.
Form what I can find online that doesn't seem to be a big problem.

The major issue will be reduce the matrix size to a manageable size.
As weapon ranges are multiples of 5 I am inclined to use a grid of that size.

Then I will be a matter of building pattern templates for the ranged weapons.
0.....0.....0.....0.....0
0....0.6...1....0.6...0
0.....1.....0.....1.....0 * Weapon Threat * (-1 if friendly)
0....0.6...1....0.6...0
0.....0.....0.....0.....0

Than you can stamp those on the matrix. As there are only a few "ranges" 25-30-35 only a couple of functions are needed.
Note the 0 at the center as units are considered to be in CC at that time.

Then you stamp the CC value of the units at the center.

At this time we get for a fictitious map something like this:
0...0...0...0...0...0...0...0
0...0...3...5...3...0...0...0
0...0...5...4...5...0...0...0
0...0...3...2..-2..-3...0...0
0...0...0..-5..-4..-5...0...0
0...0...0..-3..-5..-3...0...0
0...0...0...0...0...0...0...0

Thinking of it I guess that DoW does something similar internally but not knowing what templates are used and not being able to access the map directly restricts it's use.

Edited by VidiVici, 03 October 2007 - 10:51 AM.

[troubadour]

As it was done in mission editor why not defining a table made of circle for impassable terrain (point + radius) or made of rectangles (up left corner, down right corner)

So when you compute a straight line between 2 points you can check if it intersects one of the impassable zone instead of performing an A* search you can allow 4 steps to go around it
But it means you have to call 4 times HasThreatOnPath() for each sub steps

Problems i see :
* performance issues
* manually create a file describing all impassable zone for each maps

But it could help to solve situation like this one :

POS1 ----- DANGER
XXXXXXX - XXXXX
XXXXXXX - XXXXX
XXXXXXX - XXXXX
XXXXXXX - -------- POS2

Cause if you check your way in a straight line between POS1 & POS2 you will not see danger on the real path

Edited by troubadour, 04 October 2007 - 08:56 AM.

[VidiVici]

The problem is that those impassable zones don't seem to be available to the AI.
Also the threatmap is build in DoW as you can ask for the threat at certain positions.

But same here as I don't know how it is build I am reluctant to use it.

The goal of the A* search is to find the best 4 steps.
And as far as I know it is the most efficient algorithm at that.

PS: Thudo how is that test going?

Edited by VidiVici, 04 October 2007 - 10:59 AM.

[troubadour]

The problem is that those impassable zones don't seem to be available to the AI.
Also the threatmap is build in DoW as you can ask for the threat at certain positions.

im a going to experiment something but due to real life issue i think it will take some time (weeks)
I will create a table with coordinnates for impassable terrain for a specific map and mess HasThreatONpath() to cope with, i dont know how it will turn out imho due to performance issues i think the way Arkhan coded is the best regarding AI behavior vs Perf
Even if what i have in mind works it will be very slooooow

But same here as I don't know how it is build I am reluctant to use it.

From what i understand the table store coordinates of ennemy unit + ennemy turrets + ennemy LP (upgraded)
dont be afraid to use it

Edited by troubadour, 04 October 2007 - 12:29 PM.

[VidiVici]

im a going to experiment something but due to real life issue i think it will take some time (weeks)

Don't put to much effort into this. If the impass map is made available to the AI by Relic all your work will be useless.

From what i understand the table store coordinates of ennemy unit + ennemy turrets + ennemy LP (upgraded)

I am using that one (Let's call it the threatTable)
A threatmap must return the threat at a certain position on the map which is hidden in Relic's code atm (I think)