challenge Generate AI path for building

[madrussian 347]

@chrisb

Froggy did a pretty good job explaining the technicals, but here's my take.  I'm pretty sure it goes like this:

 

Take everyone who plays this game.  Everyone who loves the AI has wondered at one point or another why AI rarely enters buildings. Some in this pool have had trouble ordering their AI squad guys to go inside, and others have experienced them getting stuck inside.  Probably no one thinks any of that is fun.

 

Now at the other extreme, you have a much smaller pool of people to love the AI, are keenly aware of of these "indoor path-finding" issues, are good at sqf scripting, and who have run experiments (at one point or another along the way) to try to get AI in and out of buildings, using a combination of buildingPos, doMove (and WPs), and related commands.  I'm pretty sure 100% of the people who fall into this category have wound up frustrated to one extent or another (many to the point of ripping own hair out). 

 

The problem with using the engine’s indoor path-finding is that (way too often) the AI gets confused, gives up, and never arrives at it’s intended destination. (This also results in the AI getting stuck inside buildings, which to me is the biggest downer.)  Unfortunately, because this indoor path-finding is part of the engine, we don’t have visibility to tweak or fix it up.  Pierre mentions modifying the AI path LODs, a fine idea that would potentially help some cases of AI getting stuck, but probably in a very limited way.  (Modifying Path LODs seems would mostly be for situations like getting AI somewhere new, like up on the roof, etc.)

 

Along comes johnnyboy.  His method is different.  It forces the AI to move along it's path.  His method is reliable, because now the AI will get to where it’s going!  Will it be kinda janky, yes it will!  But that’s ok, because it frees us from the shackles of the engine's (limited and unreliable) indoor AI path-finding.  Perhaps most importantly, it will demonstrate to BI that we really care about issue and are willing to put our own time/effort into improving it.  If improved indoor AI path-finding isn’t already planned for ArmA4, maybe now it will get a 2nd look.

 

Btw- johnnyboy, I had this idea a couple years ago but never told anyone and now you went and stole it.  Thanks a lot, buddy.  (Lol, at the time I was just using animations to force the AI out of buildings, but they were going through the walls, etc, because I hadn’t bothered to assemble building point databases like we are trying to do now.)  I mean of course, thanks for spearheading this! 

[madrussian 347]

 

2 hours ago, mrcurry said:

Keep it up, I see great potential here, not only for AI. 

I'm curious in how you get the floor points (blue) and how do you distinguish wall from floor, is lineIntersectsSurfaces involved by any chance?

 

Thanks, and good question.  Yes, it's pretty much all lineIntersectsSurfaces.  So far, it's goes something like this:

1. Using 1 meter resolution on a 3D grid with 3 nested for loops (one for X, one for Y, and one for Z), I shoot rays straight down and record all the spots where they intersect building (by creating game logics).  Everywhere point with multiple game logics is a hit.  Then cull all the extra GLs.  (At this point it's also getting some "window sill points" and the like as you see in 1st pic, so I still need to figure out how to cull those out, which I think will happen automatically when I do the whole "group by floor" part.)
2. Turns out 1m resolution isn't enough to detect meaningful room boundaries, and we really need 0.5m.  Unfortunately, running 3D scan from step 1 with 0.5 meters is prohibitively CPU/time consuming (at least on my 7700K/16GB), so I simply "fill in the 0.5m gaps" based on the existing 1m grid (again using much smaller downward-facing rays and checking all the points for multiple GLs, again culling the extras).  At this point I've got pretty good data on "walkable surfaces".
3. Now to get room boundary:  Given any particular node, using lineIntersectsSurfaces to check LOS between points (a smidge above the floor points), I find the first edge node (which I'm calling the "keystone" node), and basically walk around the room.  So far it's quite accurate for most (all?) of the buildings in Agia Marina on Stratis (which let's admit are mostly pretty basic).  I've also had some neat surprises so far, with "rooms" being detected on top of the "open" metal roof buildings to the east in the Military Range.  I'm guessing this probably needs some (major?) tweaking to handle complex ruins, etc.

At this point I'm cautiously optimistic about achieving the end goal (which is of course usable points).  On the other hand, what pierre alluded to is right about it being super-complex, etc.  Many big challenges to be surmounted, journey might be long, outcome hangs on a knifes edge, etc. 

[chrisb 196]

7 minutes ago, madrussian said:

@chrisb

Froggy did a pretty good job explaining the technicals, but here's my take.  I'm pretty sure it goes like this:

 

Take everyone who plays this game.  Everyone who loves the AI has wondered at one point or another why AI rarely enters buildings. Some in this pool have had trouble ordering their AI squad guys to go inside, and others have experienced them getting stuck inside.  Probably no one thinks any of that is fun.

 

Now at the other extreme, you have a much smaller pool of people to love the AI, are keenly aware of of these "indoor path-finding" issues, are good at sqf scripting, and who have run experiments (at one point or another along the way) to try to get AI in and out of buildings, using a combination of buildingPos, doMove (and WPs), and related commands.  I'm pretty sure 100% of the people who fall into this category have wound up frustrated to one extent or another (many to the point of ripping own hair out). 

 

The problem with using the engine’s indoor path-finding is that (way too often) the AI gets confused, gives up, and never arrives at it’s intended destination. (This also results in the AI getting stuck inside buildings, which to me is the biggest downer.)  Unfortunately, because this indoor path-finding is part of the engine, we don’t have visibility to tweak or fix it up.  Pierre mentions modifying the AI path LODs, a fine idea that would potentially help some cases of AI getting stuck, but probably in a very limited way.  (Modifying Path LODs seems would mostly be for situations like getting AI somewhere new, like up on the roof, etc.)

 

Along comes johnnyboy.  His method is different.  It forces the AI to move along it's path.  His method is reliable, because now the AI will get to where it’s going!  Will it be kinda janky, yes it will!  But that’s ok, because it frees us from the shackles of the engine's (limited and unreliable) indoor AI path-finding.  Perhaps most importantly, it will demonstrate to BI that we really care about issue and are willing to put our own time/effort into improving it.  If improved indoor AI path-finding isn’t already planned for ArmA4, maybe now it will get a 2nd look.

 

Btw- johnnyboy, I had this idea a couple years ago but never told anyone and now you went and stole it.  Thanks a lot, buddy.  (Lol, at the time I was just using animations to force the AI out of buildings, but they were going through the walls, etc, because I hadn’t bothered to assemble building point databases like we are trying to do now.)  I mean of course, thanks for spearheading this! 

 

I can see what you are doing, its clear. Just not sure or indeed very clear how you think this will work with the ai as it stands (vanilla).

I hope your work, works, the more the ai are helped along, the better.

 

The COD thing was aimed at the poster and the response sort of confirmed that for me.

 

[johnnyboy 3797]

Well said Frogman and Mad Russian!  And to think I was ready to quit and just play A2...

 

48 minutes ago, madrussian said:

Along comes johnnyboy.  His method is different.  It forces the AI to move along it's path.  His method is reliable, because now the AI will get to where it’s going!  Will it be kinda janky, yes it will!  But that’s ok, because it frees us from the shackles of the engine's (limited and unreliable) indoor AI path-finding.  Perhaps most importantly, it will demonstrate to BI that we really care about issue and are willing to put our own time/effort into improving it.  If improved indoor AI path-finding isn’t already planned for ArmA4, maybe now it will get a 2nd look.

Hey man, we can share equally on this.  Your node map is going to be a HUGE part of this.  As someone else said, there will be alot of potential there beyond what I'm working on.

 

For feeding my "move point array", here is what I hope I can get from your nodes:

• External Entry door nodes flagged (with a center point for the door (not the door jamb), and some sort of orientation...RelDir to outside?).  We need  to ID each entry point node to use as Start Node for path calculation.
• Internal doors with center point.  This may be a hard door (with a door that must be opened), or no-door link to another room.
• Floor surface points (1 meter granularity is more than enough...although you may have needed .5 granularity for your calculations).   The less nodes the final set has, the faster the route calculation will be.
• Base of Stairs, Top of Stairs, Landing Points.  Not sure if they need special flagging, as them being Floor surface points might be good enough.
• Ladder Top and Bottom (I think we can get this already so your nodes may not need to do it).  If we can get it already, we can post-process your nodes to flag ladder points.

Nice-to-haves:

• Group nodes into  "Rooms" (so we can declare "room clear!")
• Floors we already have based on node height.
• Flag points in front of windows and dir to outside (we want to support FroggyLuv's dream of "Peeper AI").  I think we can get this another way though (I saw a script somewhere)
• Flag balcony points and dir to outside

From the above, we should be able to calculate paths:

• Using line of sight, map what nodes connect to other nodes, and record distance of node-to-node connection (or "Edge").  Actually, your node generator is already doing line of sight, so if you could capture what nodes link to other nodes (and distance between the two), that would be ideal.
• For path, ignore intermediate nodes if in straight line (minimizing nodes makes path calculation faster, and AI path execution faster).  Although we want node segments to not be more than 3 or 4 meters apart so AI has opportunity to stop and engage perceived enemies while moving.
• Calculate minimum nodes required to have visibility to all points in a room (so unit moves only the minimum distance to declare a room clear)

If we pre-calculate sweep paths per Entry, we can store the in a library and take no hit at run time.  But we can also have the full library of nodes available for real-time node-to-node path calculation (i.e., calculate evacuation route from any node on the fly, move ai from window X to window Y, etc.).

 

In other news...I started working on moving more than one unit through a path (as a stack/fireteam), and its rough going so far.  A path with no dead ends isn't bad (just run 3 guys through exact same points in order).  But when you have to clear a room, then back out to go another direction it gets hairy.  But hopefully we will prevail.  They will never be as close together as we would like though, as they seem to cause friction on each other so they run in place (even if collision allowed between all stack members). 

 

 

[madrussian 347]

@johnnyboy

Agree on all points!  (Should emphasize, this is your show & master plan.  Seriously, thanks for spearheading!)

 

12 minutes ago, johnnyboy said:

In other news...I started working on moving more than one unit through a path (stack/fireteam), and its rough going so far.  A path with no dead ends isn't bad (just run 3 guys through exact same points in order).  But when you have to clear a room, then back out to go another direction it gets hairy.  But hopefully we will prevail.  They will never be as close together as we would like though, as they seem to cause friction on each other so they run in place (even if collision allowed between all stack members). 

Wow, that sounds kick ass!  Hope you can make it work.

[madrussian 347]

3 hours ago, chrisb said:

I can see what you are doing, its clear. Just not sure or indeed very clear how you think this will work with the ai as it stands (vanilla).

I hope your work, works, the more the ai are helped along, the better.

Hopefully will work like this:  Some AI script (let's call it "main AI script") decides it wants to send AI into building.  It passes control of this AI over to johnnyboy's system, which delivers AI to interior destination (optionally having AI do cool things along the way, as seen in his videos).  "Main AI script" may have johnnyboy's do the whole indoor path at once (sending him in and back out) -or- "main AI script" may have johnnyboy's send AI in, then "main AI script" takes control again upon arrival at destination, and later passes control back to johnnyboy's to send AI back out again.
 

^ The biggest pitfall I see is when AI gets back outside.  When running my own experiments a couple years ago forcing AI out of buildings (using animations), I was having trouble getting AI to resume engine path again.  (But back then I was also unintentionally sending AI up into the air, down into the ground or objects, etc, and have many new tricks up my sleeve now).  Short answer on solution to exit is: We'll just keep pushing AI along (stuck to the ground correctly) and turning him until he resumes engine pathing on this own.  (Did I mention it might be kinda janky?)

[chrisb 196]

17 minutes ago, madrussian said:

Hopefully will work like this:  Some AI script (let's call it "main AI script") decides it wants to send AI into building.  It passes control of this AI over to johnnyboy's system, which delivers AI to interior destination (optionally having AI do cool things along the way, as seen in his videos).  "Main AI script" may have johnnyboy's do the whole indoor path at once (sending him in and back out) -or- "main AI script" may have johnnyboy's send AI in, then "main AI script" takes control again upon arrival at destination, and later passes control back to johnnyboy's to send AI back out again.
 

^ The biggest pitfall I see it when AI gets back outside.  When running my own experiments a couple years ago forcing AI out of buildings (using animations), I was having trouble getting AI to resume engine path again.  (But back then I was also unintentionally sending AI up into the air, down into the ground or objects, etc, and have many new tricks up my sleeve now).  Short answer on solution to exit is: We'll just keep pushing AI along (stuck to the ground correctly) and turning him until he resumes engine pathing on this own.  (Did I mention it might be kinda janky?)

 

Yes I see that.

 

Question would be for me, what is the enemy ai doing whilst this is all going on ?

or are they simply placed to be shot ?

or do you have something in the pipeline, that they may be doing to avoid room clearances ?

 

I know small steps, but I'm interested. 😉

 

Also, I would use the playable units to do room clearances, mainly because the enemy ai would not be stood around.

 

[johnnyboy 3797]

18 minutes ago, chrisb said:

^ The biggest pitfall I see it when AI gets back outside.  When running my own experiments a couple years ago forcing AI out of buildings (using animations), I was having trouble getting AI to resume engine path again.  (But back then I was also unintentionally sending AI up into the air, down into the ground or objects, etc, and have many new tricks up my sleeve now).  Short answer on solution to exit is: We'll just keep pushing AI along (stuck to the ground correctly) and turning him until he resumes engine pathing on this own.  (Did I mention it might be kinda janky?)

I'm experiencing that already.  With my test path I have AI sweep 2 floors and exit building, thus hopefully returning them to their normal AI.  But after leaving building they are often strangely attracted to re-enter the building using their own AI and stay there.

32 minutes ago, madrussian said:

Hopefully will work like this:  Some AI script (let's call it "main AI script") decides it wants to send AI into building.  It passes control of this AI over to johnnyboy's system, which delivers AI to interior destination (optionally having AI do cool things along the way, as seen in his videos).  "Main AI script" may have johnnyboy's do the whole indoor path at once (sending him in and back out) -or- "main AI script" may have johnnyboy's send AI in, then "main AI script" takes control again upon arrival at destination, and later passes control back to johnnyboy's to send AI back out again.

That's exactly how I envision this.  Plug and Play.  A "main AI script" could use it when desirable.  And  a mission designer can make their own paths to support any type of scenario they want (like my whacky run across rooftops, jump from building to building, etc.  You can use the generated paths per buiding, or create your own special paths.

32 minutes ago, madrussian said:

Did I mention it might be kinda janky?

"Janky" is my middle name bro!

18 minutes ago, chrisb said:

Question would be for me, what is the enemy ai doing whilst this is all going on ?

or are they simply placed to be shot ?

or do you have something in the pipeline, that they may be doing to avoid room clearances ?

That's up to mission designer, and/or "main AI Script" designer.  The core purpose of these new scripts are to sweep buildings, get an AI from point A to point B quickly and reliably, and fight along the way.  But a mission designer or "Main AI Script", can employ different paths for defending and assaulting ai groups.  Assaulting AI chooses a building sweep path.   Defending AI, once alerted, executes a defend path (move to cover stairs or door choke points), or trigger a defender evacuation route.   This puts more tools in the mission designer's tool kit.

[chrisb 196]

13 minutes ago, johnnyboy said:

That's up to mission designer, and/or "main AI Script" designer.  The core purpose of these new scripts are to sweep buildings, get an AI from point A to point B quickly and reliably, and fight along the way.  But a mission designer or "Main AI Script", can employ different paths for defending and assaulting ai groups.  Assaulting AI chooses a building sweep path.   Defending AI, once alerted, executes a defend path (move to cover stairs or door choke points), or trigger a defender evacuation route.   This puts more tools in the mission designer's tool kit.

 

I see, so it is for creating many extra positions. Which is a very good thing, if it can be done with the existing BI buildings in A3, plus of course the ai being able to handle the new positions.

All good though.

[froggyluv 2136]

On the subject of Defending AI, one great thing i think can come out of this regarding defending AI positions is the ability to set Directional AI Indoor Defense -that being from a strategic point of view perhaps in High Command giving the order to Defend the North (Winter is Coming B*tches!!) In which AI can take positions favorable from incoming from the North etc... Obviously not all building models have windows facing each direction but by using doorways, windows, rooftops, balconies etc..could be spectacular. Of course this again is up to the mission maker but as long as the nodes are there...

 

Props to you JDawg knowing my predisposition for Peeping Tom AI and people thought I was a silly COD'er pfffft

 

[madrussian 347]

"Up!  Up!  And Away!"

 

 

"Up the Stairs... To the 2nd Floor!"

 

 

It's starting to come together.  Slowly...

 

[johnnyboy 3797]

22 minutes ago, madrussian said:

"Up!  Up!  And Away!"

That is bloody beautiful man.  Really incredible.  Don't feel pressure on my end, as I have tons of work still to do.  Which make me want to recruit someone for calculating shortest path between 2 nodes.  The algorithms already exist on the web, just need someone to write the SQF.  I think I''ll throw to together some sample arrays with distance between nodes as a pre-built test case and then post a script request.  Some badass like Larrow, Grumpy or Pierre will knock it out of the park in no time.

[madrussian 347]

4 minutes ago, johnnyboy said:

I think I''ll throw to together some sample arrays with distance between nodes as a pre-built test case and then post a script request.  Some badass like Larrow, Grumpy or Pierre will knock it out of the park in no time.

 

Good idea.  Heck, we could simply use the node-mesh data from my script as the test cases (points inside the green area), on a few buildings (any building types you like).  I've been wondering how "shortest path between 2 nodes" algorithms will fare with this number of 0.5m res nodes (CPU/time wise).  I suppose there's only one way to find out!

[johnnyboy 3797]

I just whipped up some easy sample data that matches this well defined online example.  It gives them a well defined test case with expected shortest path results.  Once they claim their SQF is working we will feed it your beast!!!  That's my opinion anyway.

Spoiler

_nodes =
[
// Node, Name
[1,"Seattle"],
[2,"San Francisco"],
[3,"Las Vegas"],
[4,"Los Angeles"],
[5,"Denver"],
[6,"Minneapolis"],
[7,"Dallas"],
[8,"Chicago"],
[9,"Washington DC"],
[10,"Boston"],
[11,"New York"],
[12,"Miami"]
];
_connections =
[
// FromNode, ToNode, Distance
[1,2,1306],
[1,5,2161],
[1,6,2661],
[2,3,919],
[2,4,629],
[3,4,435],
[3,5,1225],
[3,7,1983],
[5,6,1483],
[5,7,1258],
[6,7,1532],
[6,8,661],
[7,9,2113],
[7,12,2161],
[8,9,1145],
[8,10,1613],
[9,10,725],
[9,11,383],
[9,12,1709],
[10,11,338],
[11,12,2145]
];

 

 

[The Real Bunc 137]

@Johnnyboy what you are looking at is essentially the travelling salesman problem is it not in regard to shortest path calculations on a network? From memory I think exact algorithms to give a perfect solution are very computationally expensive particularly if there are a lot of nodes? There are supposed to be approximate algorithms and heuristics though that can give good results in more reasonable time though. Maybe if there is someway to "throw away" nodes which are less likely to be useful ( eg ones which are immediately proximate to walls etc) then the problem might be made more tractable? Just a thought.

[johnnyboy 3797]

I've posted the Shortest Path Challenge here:

 

14 minutes ago, The Real Bunc said:

@Johnnyboy what you are looking at is essentially the travelling salesman problem is it not in regard to shortest path calculations on a network? From memory I think exact algorithms to give a perfect solution are very computationally expensive particularly if there are a lot of nodes? There are supposed to be approximate algorithms and heuristics though that can give good results in more reasonable time though. Maybe if there is someway to "throw away" nodes which are less likely to be useful ( eg ones which are immediately proximate to walls etc) then the problem might be made more tractable? Just a thought.

Exactly.  I'm hoping MadRussian will be able to prune unneeded nodes once he has the rooms well defined.  IMO, for AI path purposes we only need nodes every 2 or 3 meters, plus all connector nodes (doors, stairs, ladders, etc.), and strategic points (corners, windows). 

 

If path calculation is too slow at game run-time, then we can run shortest sweep path calculations per entrance per building, and store the paths in the arrays.  We would include all these pre-calculated path arrays in a path library file with the scripts.  So at run-time, building clearing paths are all ready to rock.  But if we want to support dynamic point to point pathing, then we need the full node library per building and real time path calculation.  I'm pretty sure we can do the former, and if we're lucky we can do the latter.

[The Real Bunc 137]

Ive been following this with great interest and I understand what you are trying to achieve. Re travelling salesman problems my understanding is that humans actually find "good enough " shortest paths actually as efficiently as algorithms. That would suggest to me that given there are a limited number of buildings that player traced paths which where then stored ( someone already has something on this I think?) seem at least in part a solution. I know you are trying to attempt a solution with maximum flexibility and its almost a programming challenge as much as anything but I wonder if some sort of combined approach might turn out to be a good solution. ie one which allows for players to do walkthroughs of buildings which record paths but with flexibility for novel node following algorithms to find other paths. I also think if you can find a way to throw away some nodes early in an algorithm this might simplify the task.   As an example - the building position approach as has been noted has its drawbacks - not least because these positions are often at the edges of rooms. If you want a path to traverse a room then they aren't very useful. Equally if the task is to traverse the room you don't need to check all the nodes at the room edges as buildings are mostly empty. so if you can throw away all the corner nodes (other than ones adjacent to doors or windows perhaps) and nodes running along the walls you have a much smaller node network to traverse to find the shortest path. Anyway that's just some thoughts trying to be helpful. If its not helpful just ignore me!

[johnnyboy 3797]

2 minutes ago, The Real Bunc said:

. ie one which allows for players to do walkthroughs of buildings which record paths but with flexibility for novel node following algorithms to find other paths.

I'm supporting player walkthrough path recording right now.  That is how I've built my testing paths.  And I plan to keep this feature as it allows editor to make any path anywhere for cutscenes, etc. (i.e., my example running across 3 building roofs, jumping to another roof, jumping down to a van...was all one path I recorded).  I think editors will have a lot of fun creating their own novel paths.

4 minutes ago, The Real Bunc said:

If you want a path to traverse a room then they aren't very useful. Equally if the task is to traverse the room you don't need to check all the nodes at the room edges as buildings are mostly empty. so if you can throw away all the corner nodes (other than ones adjacent to doors or windows perhaps) and nodes running along the walls you have a much smaller node network to traverse to find the shortest path.

Agreed.  Ultimately we only need AI to travel to those nodes that allow him to clear a room.  In a perfectly square room, you can see the entire room, so a single node in the room suffices for clearing (plus connector nodes at doors).  If a room has an adjacent alcove you can't see when entering room, then you need at least 2 points in the room to clear it (my first video shows first room entered has an alcove to the left that AI must approach before having line of sight to it).  We also want nodes at 3 meter intervals.  My AI can't engage targets while moving, so allowing them to stop every 3 meters (only if they sense enemies) allows them to defend themselves.  If no enemies detected, they move pretty quickly through the 3 meter intervals.

7 minutes ago, The Real Bunc said:

Anyway that's just some thoughts trying to be helpful. If its not helpful just ignore me!

I appreciate your inputs and interest.  Keep 'em coming!

[madrussian 347]

13 hours ago, The Real Bunc said:

I also think if you can find a way to throw away some nodes early in an algorithm this might simplify the task.   As an example - the building position approach as has been noted has its drawbacks - not least because these positions are often at the edges of rooms. If you want a path to traverse a room then they aren't very useful. Equally if the task is to traverse the room you don't need to check all the nodes at the room edges as buildings are mostly empty. so if you can throw away all the corner nodes (other than ones adjacent to doors or windows perhaps) and nodes running along the walls you have a much smaller node network to traverse to find the shortest path.

 

13 hours ago, johnnyboy said:

Ultimately we only need AI to travel to those nodes that allow him to clear a room.  In a perfectly square room, you can see the entire room, so a single node in the room suffices for clearing (plus connector nodes at doors).  If a room has an adjacent alcove you can't see when entering room, then you need at least 2 points in the room to clear it (my first video shows first room entered has an alcove to the left that AI must approach before having line of sight to it).  We also want nodes at 3 meter intervals.

 

Just so we're all on the same page, the whole "gazillion nodes" is not so we can store them.  It's so we can get an accurate outline of each room.  (In fact, we might not even need to store any of them.)  The more (detection) nodes the merrier!  I envision the final solution (my part) as a collection of room and stairs outlines and a handful of quick optimized functions that given a set of ultimate start and end points, can dynamically pick intermediate points and determine a viable path from one point to another, perhaps even very quickly.  In other words, these pathing functions might even be suitable to call at runtime (particularly because they are not crunching through gazillions of nodes).  Of course, I'm hoping that's what I can deliver and only time (+ more effort) will tell.

 

In other news, I highly optimized the floor detection.  Now gets by with single initial 2D raycasting pass (followed by second focused pass that trims out junk points).  No more inefficient 3D mega first pass at 1m plus 2nd pass "filling in the gaps" to get to 0.5m.  We can go straight to 0.3333m right off the bat now, and it's super quick!  0.25m takes a bit longer but not too bad.  (Even lower is viable, trading off increased time for better resolution the lower you go.)

 

[johnnyboy 3797]

2 minutes ago, madrussian said:

Just so we're all on the same page, the whole "gazillion nodes" is not so we can store them.  It's so we can get an accurate outline of each room.  (In fact, we might not even need to store any of them.)  The more (detection) nodes the merrier!  I envision the final solution (my part) as a collection of room and stairs outlines and a handful of quick optimized functions that given a set of ultimate start and end points, can dynamically pick intermediate points and determine a viable path from one point to another, perhaps even very quickly.  In other words, these pathing functions might even be suitable to call at runtime (particularly because they are not crunching through gazillions of nodes).  Of course, I'm hoping that's what I can deliver and only time (+ more effort) will tell.

Sounds perfect man!  Getting excited...

[madrussian 347]

Hey all, small progress update.  I refactored the detection algorithms, and it works pretty well on more complex structures now.  More importantly, we have our first usable points, stair tops and bottoms!

(Btw - Stair detection wasn't trivial like we'd hoped.  Had to filter out several types of false-positives.)

 

Here's a quick real-time video:

[For added fun, listen to this simultaneously as soundtrack.]

 

 

Closeups of the new stairwell points:

Note - All the rays have to be raised quite a bit over visible surfaces (in order to see them), unlike the nodes (in this case yellow, which are positioned as they appear).

 

 

[Defunkt 431]

It's great work you're doing. I'm a big fan of offline indexing for optimal in-game results both in terms of quality but especially performance. This might just end up being the biggest upgrade to Arma since its release.

[The Real Bunc 137]

That's impressive. Its a generated 3d floor plan.  

[johnnyboy 3797]

2 hours ago, madrussian said:

Hey all, small progress update.  I refactored the detection algorithms, and it works pretty well on more complex structures now.  More importantly, we have our first usable points, stair tops and bottoms!

(Btw - Stair detection wasn't trivial like we'd hoped.  Had to filter out several types of false-positives.)

That is fantastic man...I'd say that is great progress.  I never doubted it was hard honestly.  Those stair detection points are critical, so thanks much for that.  And a most excellent choice for accompanying music...every song on that album is great.

 

I'm making progress as well.  I now have 3 guys moving fairly close together through a building.  Lots of special situations to handle (reverse direction after clearing a dead end, keeping close together instead of each follower robotically  staggered one waypoint behind the leader, etc.).  Lots of fine tuning to do, and need to test on more buildings to insure current build works in more circumstances.  Anyway I'm still fairly confident we will have decent end product.

[madrussian 347]

Ok, got some time today and took all my spaghetti code and made it into an proper system (broken into parts, etc).  Because it was getting crazy scrolling up and down through one giant init file.  Next up, somewhat in order:

 

1. Fix a couple (semi-trivial?) bugs I found trying it on other ruins.
2. Split the collections up by floors/rooms.  This is tricky, because for instance see that pic of how the bottom of the stairs outline (yellow rays) and the collection outlines (green rays) don't line up?  I think I know how to tackle this:  Get the initial collections.  Then get stairs and "choke point areas" (think doorless doorways).  Then dump the initial collections and rebuild them, now with the stairs and "choke points areas" as the new boundaries between the collections.  This will line up the outlines properly and should give us the coveted Rooms (by floor).

3. Get all the Perceived Entry Points (PEPs), for first floor only.  (Which is probably the best I can do, for buildings like those ruins missing entire walls, etc)

4. Tackle actual doors.  Detecting them, assigning them to Rooms, etc.  Thankfully, actual doors already act as boundaries between collections (for collection detection purposes).

5. Figure out what we actually need to store.  I know johnnyboy you would prefer simple paths, as that's what your script uses to move the AIs.  OK, more on what I envision pathing-wise once I have more to show.