challenge Generate AI path for building

[johnnyboy 3797]

Maybe one of you scripting/geometry gurus can write a script that generates move positions for a particular building model.  For a building type, we can currently detect Building Positions, and Doors.  But that is not enough positions to calculate a path for a scripted AI to move through (see topic JBOY Scripted Path).  What I am hoping is possible, is to do the following:

• Find External Doors (entrances to buildings).  Pick one External Door to be beginning of path.
• Create position on outside of door (outside building) (Red Marker 1 in screenshots below).
• Create position inside of building (Red Marker 2)
• Ray cast around, can entire room be seen from this inside position? 
• Locate interior door or transitions to other rooms by line of sight and capture position.
• Bottom line, calculate a path as presented in the ordered Red markrs below.

Key for screenshots:

• Yellow markers in door jambs are door positions (which we can get now)
• Blue markers are Building Positions we can get now (but may be of no use to Scripted AI Paths)
• Red markers are Positions we hope can be calculated to make a path through a building.  They are numbered 1 through N to simulate the path we want AI to travel to clear rooms.

For this building, we find an external door, and use that to calculate starting position of path: Two positions should be calculated (one outside door (1), and one inside door(2)).

Then we enter the building.  From here the layout is analyzed and find that we need to connect to the internal hallway across the room.  There is no hard door, but we want a position calculated inside room we are in, and other side of door in hallway (positions 3 and 4 by the internal door).  From position 4 we can see the whole hall way so do not have to go further down the hallway.  Next we detect that this is a two story building, so we must find the bottom of the stairs (6), the landing corner (7), and the top of the stairs (8).  When we know bottom of stairs (6) we need to connect our path from the hallway (4) to bottom of stairs (6).  But this cannot be a straight line, because there is a wall blocking line from 4 to 6.  So we calculate an intermediate position (5) in the room (so AI can walk from hallway (4)  through position (5) then to bottom of stairs (6) -- i.e position 5 can see both 4 and 6 unobstructed).

 

Next we move up to second floor.  We have top of stairs position (8).   This is a divide room, so position 8 cannot see entire room behind partial wall.  So calculate the next position (9) which allows full unobstructed view of upper side room.  Once he have position 9 we can see all the upstairs except for side room that has a physical door (position 10).  Calculate a position on either side of door (10 and 11).  Then AI can enter this 2nd floor side room.

 

Once inside second floor side room (11), we need a position inside room (12) where we can see entire move for clearing.   For clearing we may not need position 13 but maybe we want to move there because of the window.  Not sure about that.

If we were able to calculate all of the above, then an AI could clear every room in this 2 story building.

 

BUT, this building has a back entrance also (see below).  So we would want to calcualte a path for walking this building from this alternate entrance also.  So beginning position outside door (1), another path is analyzed to walk the same building.  Maybe if we already have a path segment for going upstairs, it only needs to calculate new path to position 4.  And then it would use the same path segment to go upstairs that was previously calculated.

 

This is some crazy stuff and I don't know if its doable.  Maybe one of you cool geniuses out there can do it!!! 

Good luck!!!!

 

 

[johnnyboy 3797]

Watch this video to see how we want to use the generated positions to have an AI clear a building.  The script used in this video has hardcoded positions for all the red arrows.  If only these positions could be calculated for each building!!!

 

[GEORGE FLOROS GR 4207]

This is pretty cool Johnnyboy !

 

My though is ,

do the building positions have a particular id or number and if so then i think it would be an easy way to set the ai to walkthrough.

 

any idea about it ?

[GEORGE FLOROS GR 4207]

this is from BTC:

private ["_group","_house","_wp","_allpositions"];

_group = _this select 0;
_house = _this select 1;

_allpositions = _house buildingPos -1;
if (btc_debug_log) then {diag_log format ["setWaypoint : count all pos %1 in %2 ", count _allpositions,_house];};
{
	_wp = _group addWaypoint [_x, 0];
	_wp setWaypointType "MOVE";
	_wp setWaypointCompletionRadius 0;
	_wp waypointAttachObject _house;
	_wp setWaypointHousePosition _foreachindex;
	_wp setWaypointTimeout [15, 20, 30];
} forEach _allpositions;

 

[johnnyboy 3797]

3 minutes ago, GEORGE FLOROS GR said:

do the building positions have a particular id or number and if so then i think it would be an easy way to set the ai to walkthrough.

 

Building positions are sparse, and if you connect straight lines between the positions, AI would ghost through walls.

[johnnyboy 3797]

1 minute ago, GEORGE FLOROS GR said:

this is from the BTC:

I'm aware you can have AI navigate through Building Positions.  But the AI is slow doing that, and you can't get them to clear a room as a team. With this new scripted AI approach we can have them move fast, and perform any special action we want at each point (open door, throw grenade, sidestep to evade grenade damage, use shotgun to breach locked door, use charge to breach locked door, climb a ladder to the next floor, walk across a plank to the roof of another building...anything at all really).

[GEORGE FLOROS GR 4207]

3 minutes ago, johnnyboy said:

But the AI is slow doing that

 

Yes that's true.

 

Maybe mad_cheese know already something about ?!

There is much CQB action with C2 -Command And Control

 

On 7/7/2018 at 3:13 PM, mad_cheese said:

Here's a playlist with more new videos, didn't feel I should keep posting each single one on it's own

 

 

[genesis92x 810]

If there is a dynamic way to create waypoints/positions for AI to path through buildings, I would love to see it. 

[johnnyboy 3797]

54 minutes ago, genesis92x said:

If there is a dynamic way to create waypoints/positions for AI to path through buildings, I would love to see it. 

Hey genesis.  I have big respect for your vcom ai work, and know you know a lot about available building data.

 

My thoughts on generating ai path is it may be possible by plotting rooms via some sort of ray casting.  We should be able to find external doors by finding doors nearest outside of bounding box with N/S/E/W relative orientation.  We can calculate # of floors by Building Position's relative height.  Maybe from each building position a rectangle area is calculated via ray casting and room dimensions can be calculated.  Where Room Rectangles overlap we may have corners.  If we calculate room rectangles, then we can calculate the center of each rectangle.  From centers of adjacent rectangles if there is no line of sight between the 2 centers, then we try and find a right angle corner position that has line of sight to each rectangle.  Where room rectangles overlap with internal doors, we have passage ways. If the builing has >1 floors, you raycast around 1st floor room at 1 meter above floor and 1.5 meters above floor.  If the 1 meter ray's distance is less than  the 1.5 meter ray's distance you have found a slope that may be stairs.

 

Assuming all  that works, I wouldn't expect real time path calculation in game.  Instead we use the algorithm to pre-calculate paths one time and store them off in arrays.  Then our movement scripts run off a library of pre-defined path arrays per building.

 

Its easy for me to say because I don't plan on doing this work, lol (for now I'm focusing on my movement script).

 

Those are my hopes. 

[pierremgi 4889]

Hi, First of all, how do you order a unit to move to the exact position (existing buildingPos)?

I failed with a simple "Land_i_Shop_01_V3_F" . I can place arrow helpers on positions but no way to make the unit move to exact positions. I tried with addWaypoint, addWaypoint ASL pos and radius -1, doMove...

The unit stops when he considers the move as done (and returning true for unitReady...).

[johnnyboy 3797]

17 minutes ago, pierremgi said:

Hi, First of all, how do you order a unit to move to the exact position (existing buildingPos)?

I'm cheating:

Spoiler

//scootAndShoot.sqf
// to compile: JBOY_scootAndShoot =  compile preprocessFileLineNumbers "JBOY_SnS\scootAndShoot.sqf";
params["_dude", "_anim", "_travelMeters","_isFiring","_shootIterations"];
_dude setVariable ["busy", true,true];
//sleep 1;
_dude disableai "ANIM";
_startPos = getposasl _dude;
_dude playmove _anim;
if (_isFiring) then
{
	_dude setbehaviour "COMBAT";
	_logic = createGroup west createUnit ["Logic", [0,0,0], [], 0, "NONE"]; 
	_n = [_dude, _logic,_shootIterations] spawn
	{
		params["_dude","_logic","_shootIterations"];
		sleep 1; // give unit time to raise his weapon in combat mode
		for "_i" from 1 to _shootIterations do
		{
			_logic action ["useWeapon", _dude, _dude, 2];  // 2 is burst mode
			sleep .3;
		};;
	};
};
waituntil {(_dude distance2D _startPos >= _travelMeters-1) or !alive _dude};
//_dude switchMove "";
_dude enableAI "ANIM";
_dude setVariable ["busy", false,true];

 

Unit must be turned in direction towards position to move to before calling the above.

[pierremgi 4889]

wow! your challenge seems to me resource consuming, then. But I appreciate the brain storming!

[johnnyboy 3797]

Just now, pierremgi said:

wow! your challenge seems to me resource consuming, then. But I appreciate the brain storming!

It probably would be resource consuming to build a path for a building.  So we would run it as developers and collect paths per building in one big library script.  This library script could then be used by mission designers, the path would already be generated, so need to re-calculate it at mission run time.

[GEORGE FLOROS GR 4207]

On 4/13/2019 at 5:37 PM, pierremgi said:

I failed with a simple "Land_i_Shop_01_V3_F"

Since the general disscusion is about path in buildings ,

i was trying to do this , with waypoints as well and it was not working as it should be all the times.

 

I noticed that it is depending on the building.

There were also some buildings , that the ai didn't move to them at all.

 

Here is my code :

Spoiler

GF_Clear_House_wp = {


private ["_group","_house","_wp","_positions"];

_group = _this select 0;
_house = _this select 1;

if (({alive _x} count units _group) < 1) exitWith {};

_positions = _house buildingPos -1;
hint format ["%1 positions for house : %2 ", count _positions,_house];

_group setFormation "COLUMN";

{
	_wp = _group addWaypoint [AGLToASL _x,-1];
	_wp setWaypointSpeed "LIMITED";
	_wp setWaypointFormation "COLUMN";
	_wp setWaypointType "MOVE";
	_wp setWaypointCompletionRadius 0;
	_wp setWaypointPosition [AGLToASL _x,-1];
}forEach _positions;


	_loop = true;
	while {_loop} do{

		uisleep 10;
		
		if (({alive _x} count units _group) < 1) exitWith {};
		
		if (speed leader _group isEqualto 0) exitWith {
			systemchat "Group not moving";
			{deleteWaypoint((waypoints _group)select 0);}forEach waypoints _group;
			[_group] call GF_Clear_House;
			systemchat"exit loop";
		};
		
		_index = currentWaypoint _group;
		_count = count (waypoints _group);
		
		if!(_index isEqualto _count)then{
			systemchat format["index : %1",_index];
			systemchat format["waypoints : %1",(count (waypoints _group))];
			_loop = true;
			uisleep 1;
			
		}else{
			{deleteWaypoint((waypoints _group)select 0);}forEach waypoints _group;
			[_group] call GF_Clear_House;
			systemchat"exit loop";
			_loop = false;
		};
	};
};


GF_Clear_House = {

systemchat "Clear_House";

private ["_group","_house","_wp"];

_group = _this select 0;
if (({alive _x} count units _group) < 1) exitWith {};

_nearestObjects = nearestObjects [_group, ["House", "Building"], worldsize];
_house = selectrandom _nearestObjects;

[_group,_house] call GF_Clear_House_wp;

_group setFormation "COLUMN";

_wp = _group addWaypoint [getPosATL _house,0];
_wp waypointAttachObject _house;
_wp setWaypointHousePosition 0;
_wp setWaypointCompletionRadius 0;
};

[g1] call GF_Clear_House;

 

 

 

Something that i want to ask is that i tried both :

_wp setWaypointPosition [_x, 0];

_wp setWaypointPosition [_x, -1];

but the -1 was not giving as said the exact position.

Might be that i'm doing something wrong ?

Thanks !

[pierremgi 4889]

Yep! the radius -1 implies ASL position. you need to use AGLToASL...

 

Here is the way I sweep a building with a unit. Place it in front of a house, name it bob, and follow it.

 

0 = bob spawn {
  params ["_unit"];
  _initPos = getPosASL _unit;
  _init0 = _initPos;
  _nearHouse = (nearestTerrainObjects [_unit,["house"],100] select {count (_x buildingPos -1)>0} select 0);

  _bPos = _nearHouse buildingPos -1;

// _bPos is the building position array

  for "_i" from count _bPos -1 to 0 step -1 do {

// I apply on positions 2 filters: first one for level/stage of the building, second one for the nearest position from the last treated
    _bPosArr = _bPos apply {[round ((2+(AGLToASL _x select 2))/2), _initPos distanceSqr AGLToASL _x,_x]};
    _bPosArr sort true;

// I'm using the precise waypoint coordinate with radius -1 (no need to use setWaypointHousePosition)
    _wp = group _unit addWaypoint [AGLToASL (_bPosArr select 0 select 2),-1];
    _wp setWaypointTimeout [0.5,0.5,0.5];

// deleting the used position as I'm sorting again for nearest pos
    _initPos = AGLToASL (_bPosArr select 0 select 2);
    _bPos = _bPos - [_bPosArr select 0 select 2];
  };
 group _unit addwaypoint [_init0,-1];

// follow the arrow as test
  _boo = createVehicle ["Sign_Arrow_Yellow_F",[0,0,0],[],0,"can_collide"];
  _boo spawn {
    while {true} do {
      _this setpos waypointPosition [group bob,currentWaypoint group bob];
    };
  };
};

Sometimes (not so often) the guy is stuck in door frame, especially when investigating balcony.

Vanilla AI is opening doors and don't pass thru walls, as I tested so far.
The building level/stage filter seems fine but can be optimized.

The nearest next position works fine also but sometimes the path to reach it is ... amazing. I think there is nothing to do except for scripting paths inside a modded building. I don't know how to do that. But that could be clearly the alternate solution for Rube Goldberg JohnnyBoy script. 

[johnnyboy 3797]

1 hour ago, pierremgi said:

know how to do that. But that could be clearly the alternate solution for Rube Goldberg JohnnyBoy script. 

Oh yee of little faith...   We're gonna crack this bitch wide open., you wait and see!

[madrussian 347]

Very excited about this idea!  Here's how I would approach, per building:

1. Get a list of internal rooms (detected using a series of randomly positioned raycasting "bombs"), obtaining the bounding box for each room. [moderately hard but doable]
2. Find and frame the openings between rooms (detected with a grid of parallel raycasts along each wall). [moderately hard but doable]
3. Determine which of these openings between rooms are doorways, and which are simply "holes in the wall" (using the data from step 2). [semi-easy]
4. Find and frame the external windows (again detected with a grid of parallel raycasts along each wall). [moderately hard but doable]
5. Get all the "standing directly in the middle of the doorway" points (easy).
6. Get all the "standing in front of the doorway" points (semi-easy).
7. Get all the "standing in front of the window" points (semi-easy).
8. Detect the stairwells and get the two important points (top and bottom). [might take quite a bit of effort, but should be doable]
9. Get "nav-mesh style grid info" for each room, by find the obstructions within each room (beds, dressers, cabinets, sinks, bathtubs, etc), again detected with a grid of parallel raycasts, this time facing down from the ceiling [moderately hard but doable]
10. Pick some random navigation points within each room using the "nav-mesh style grid info". (easy)
11. Organize all the points, "connecting the dots" so to speak (with info on floors, type of point, etc), making sure to raycast between them to ensure the connections.  For use by our illustrious AI script creators. 

Then some "rooms" are missing a wall (like destroyed church), and some rooms have an extra diagonal wall (like that town-center corner building), so we'd have many edge cases.  Then we have all the external "rooms" (like balconies, rooftops, etc), which would obviously be more challenging.  The whole endeavor would require quite an iterative approach.  Start with the easy stuff first, then work our way up.

 

Side questions - Anyone recall if Arma building internal doors are detectable?  Does anyone know if DayZ ever implemented indoor path-finding?  I seemed to recall they pretty much canned AI from the mod tools.  But how does indoor path-finding work for the AI zombies? (as compared to ArmA3 indoor AI path-finding).  Curious, as that may be an indicator of how Arma4 indoor AI path-finding will end up.

 

Anyhow, back to the here and now.  Seems to me we have the tools to make this happen:

Quaternion Rotation functions

 

Btw - I'm not necessarily volunteering!  But I might just run a few experiments to (you know) see if we can get this ball rolling, and see where it goes. 

[pierremgi 4889]

@madrussian Is this a job interview for BI dev? Because you're the right man!

You just have to replace:

- "easy" by "assigned to"

- "semi-easy" by "need more info"

- "moderately hard but doable" by "duplicated" or "closed"

 

 

[.kju 3245]

a) Manually record the paths and positions yourself as the player and store the data.

or

b) Use external tools to load in the p3d data, use external programming languages and libraries to determine all the information and store the data.

[pierremgi 4889]

Just a point... or 2. In house, between PtA and PtB, your unit will not have a path, if there is no defined path LODs.

You can experience that with buildingPos.

Usually, but not always, it's possible to navigate (for AI) inside a building which have positions. But sometimes, if you order a move (addWaypoint or else) between 2 close positions, the AI will walk a large detour, up/downstairs or even by exterior.

So? If I'm right, you are discussing about points... What about path LODs? 

[johnnyboy 3797]

32 minutes ago, .kju said:

a) Manually record the paths and positions yourself as the player and store the data.

or

Thanks for the suggestions kju.  I'm already working on a utility for that, where I use on a Fire eventhandler on player to record a position in my move array format.  So mission designer walks to each position and shoots once, and position is recorded in array. Walk through all desired positions then paste array into a script and path is captured.  This works.  And its how I recorded the path you see the AI follow in the video.

 

32 minutes ago, .kju said:

b) Use external tools to load in the p3d data, use external programming languages and libraries to determine all the information and store the data. 

Good idea, but beyond the level of work I am willing to put into this.

 

7 minutes ago, pierremgi said:

Just a point... or 2. In house, between PtA and PtB, your unit will not have a path, if there is no defined path LODs.

You can experience that with buildingPos.

True. That is why I want my own path positions not using building positions.  The video demonstrates how this works well without using Building Positions.  This is why I hope to calculate my own line of sight paths through building.  If not possible, then we record and hardcode paths per building like I did for the video.

 

7 minutes ago, pierremgi said:

So? If I'm right, you are discussing about points... What about path LODs? 

Yes, I want the "points".  LODs may be a good idea, but I am not familiar with looking at LOD data.

[madrussian 347]

2 hours ago, pierremgi said:

@madrussian Is this a job interview for BI dev? Because you're the right man!

You just have to replace:

- "easy" by "assigned to"

- "semi-easy" by "need more info"

- "moderately hard but doable" by "duplicated" or "closed"

All jesting aside, in terms of creating an automated system to gather the building position data:  My point was if you break that portion down into individual steps, no one step is really all that hard.

 

Now, getting the AI to use those points effectively, and not collide with each other, etc, yeah that's hard!  Good thing johnnyBoy signed up for that part. 

 

Anyhow, I think his system is quite promising and a worthy endeavor.  Because let's face it, using buildingPos & doMove (& relying on path-lods) and watching the AI freak out, run in circles, and get trapped in buildings sure ain't cutting it.

[chrisb 196]

Did this do something similar: http://www.armaholic.com/page.php?id=27305

[johnnyboy 3797]

2 hours ago, madrussian said:

Btw - I'm not necessarily volunteering!  But I might just run a few experiments to (you know) see if we can get this ball rolling, and see where it goes

Your breakdown of tasks is quite good, and very close to what I was thinking as well.  I believe it is possible.  I was thinking for each floor, take a Building position nearest to the building's position.  This is just to get one inside point that is on the floor and not in a wall.  Create a point there.  Then ray cast out in N,S,E,W and create a point every .5 meters that is within the walls.  Move to the next adjacent point and do the same thing.  Do not record duplicate points.  Once done you have points covering the floor, and not outside the walls.  It may not be a perfect rectangle, because this method would fill in points in adjacent alcoves/hallways/etc also.  We also have doors calculated so we put hard point there at center of door and either side of door as you say.  Then out of all the floor points, I want to isolate which ones link adjacent rectangles with line of sight (a point that can see the main room and the alcove).  Create a hard point there.  Create a hardpoint at center of each room rectangle also.  Once we have these hardpoints, we should have the least amount of points needed for AI moves that guarantee clear visibility path (unobstructed walking path)  to each rectangle (like side alcoves).   We then discard all the unused .5 meter points that we don't need for pathing.  Per hard point collected, I would also store list of the other hard points (nodes) that the point has line of sight to.  We could then develop an algorithm to find shortest path from one point to another.  And develop an algorithm for calculating shortest path that clears entire house.
 

Stairs can be detected like I described earlier:  Cast pairs of rays (one .2 meters high and one .6 meters high).  If lower ray's distance to wall is shorter than higher ray's distance to wall, then we have a slope that may be a stair.  I haven't thought this all the way through, but it seems doable.  Our rays then march up the stairs to find either a flat landing or the next floor.

 

Anyway, I hope its doable and I would love it if some mad russian  took it on!!!!  Thanks for your interest and thoughtful insight into the problem regardless.

[johnnyboy 3797]

12 minutes ago, chrisb said:

Did this do something similar: http://www.armaholic.com/page.php?id=27305

Thanks Chrisb.  I believe that works differently and has a different purpose.  It will exactly capture every move, direction and firing for a unit, creating a huge playback file to be played.  This is great for making a movie, or some scripted sequence where there is no dynamic AI attacking the unit playing the script.  With this unitPlay script, the unit ignores any near enemies.

 

With my script we are recording a series of positions, and unit may pause at each position.  When pausing at a position unit will use his normal enemy detection/targeting/fighting AI and engage any enemy.  So we record much smaller path files (20 or less positions can clear a house), and unit can engage any enemy it encounters.