Jump to content


  • Content Count

  • Joined

  • Last visited

  • Medals

Community Reputation

164 Excellent


About madrussian

  • Rank
    Master Sergeant

Recent Profile Visitors

The recent visitors block is disabled and is not being shown to other users.

  1. Gotcha, that makes sense. OK if I have many nodes, I'll go ahead and pair it down to squeeze out max performance!
  2. Hi all, quick update. Made a little progress, here's a quick video! (~ 9min) (For added fun, play this for soundtrack while watching...) ^ OK, that was fully automated and how it looks when everything goes right. The system is using refined chokepoints now (which are working extremely well now across different building types), plus refined window points & refined entry points (both of which are extremely WIP on other buildings... but lol happen to work very well in this here pub). In other words please don't be fooled, as at the moment not every building does anywhere near this well. At the end I used Sarogahtyp's Simple Shortest Paths Dijkstra (for that last "rifle icons" bit). Thanks again Sarogahtyp! Here are the points from that last run generated for ye ole "Land_A_Pub_01" (in building model space), ready to go: _nodesList = [[0,[5.50879,-5.24146,-5.77265]],[1,[-1.36621,-6.34155,-5.77265]],[2,[-2.46631,0.808594,-5.77265]],[3,[-0.816406,-4.11401,-5.77265]],[4,[-0.816406,0.781006,-1.78779]],[5,[6.3335,2.98096,-1.78779]],[6,[6.3335,1.38599,-1.78779]],[7,[0.53125,-6.06665,-1.78779]],[8,[-1.06372,-6.06665,-1.78779]],[9,[-2.21875,-5.51636,-1.78779]],[10,[-3.81372,-5.51636,-1.78779]],[11,[-2.21875,-5.51636,-5.77265]],[12,[-3.81372,-5.51636,-5.77265]],[13,[-1.06372,0.533447,-5.77265]],[14,[1.08105,0.533447,-5.77265]],[15,[0.283691,-1.1167,-5.77265]],[16,[0.283691,-3.01392,-5.77265]],[17,[4.68359,2.48608,-5.77265]],[18,[4.68359,4.08105,-5.77265]],[19,[1.93359,4.08105,-5.77265]],[20,[1.93359,2.6416,-5.77265]],[21,[0.833496,-3.61914,-5.77265]],[22,[0.833496,-4.96631,-5.77265]],[23,[0.833496,-4.96655,-5.77265]],[24,[0.283691,-6.31396,-5.77265]],[25,[0.833496,-5.76392,-1.78779]],[26,[0.833496,-4.16895,-1.78779]],[27,[6.60864,7.40845,-1.78779]],[28,[6.60864,-3.0415,-1.78779]],[29,[5.50879,-5.24146,-1.78779]],[30,[-7.14136,-6.34155,-1.78779]],[31,[-7.14136,0.808594,-1.78779]],[32,[-3.84131,-6.34155,-5.77265]],[33,[-7.14136,0.808594,-5.77265]],[34,[0.00878906,6.8584,-5.77265]],[35,[6.60864,4.1084,-5.77265]],[36,[6.60864,-0.291504,-5.77265]],[37,[6.60864,3.28345,-1.78779]],[38,[6.60864,1.0835,-1.78779]],[39,[6.60864,-1.11646,-1.78779]],[40,[3.5835,-6.34155,-1.78779]],[41,[1.38379,-6.34155,-1.78779]],[42,[-1.9165,-6.34155,-1.78779]],[43,[-5.21631,-6.34155,-1.78779]],[44,[-4.6665,0.808594,-1.78779]],[45,[-1.9165,0.808594,-1.78779]],[46,[-6.31641,-6.34155,-5.77265]],[47,[-4.6665,0.808594,-5.77265]],[48,[0.00878906,4.93335,-5.77265]],[49,[6.60864,6.5835,-5.77265]],[50,[0.00878906,4.93335,-1.78779]],[51,[0.00878906,7.13354,-1.78779]]]; _connectionsList = [[0,16],[0,17],[0,21],[1,3],[1,11],[2,11],[2,13],[3,4],[3,1],[3,11],[4,3],[4,45],[5,6],[5,37],[5,50],[6,5],[6,29],[6,38],[7,8],[7,25],[7,41],[8,7],[8,9],[8,42],[9,10],[9,8],[9,42],[9,45],[10,9],[10,30],[10,43],[10,44],[11,12],[11,1],[11,2],[11,3],[12,11],[12,32],[12,46],[13,14],[13,2],[14,13],[15,16],[16,15],[16,0],[16,21],[17,18],[17,0],[17,36],[18,17],[18,19],[18,35],[19,20],[19,18],[20,19],[21,22],[21,0],[21,16],[22,21],[22,23],[23,22],[25,26],[25,7],[25,29],[25,40],[25,41],[26,25],[28,29],[28,39],[28,40],[29,6],[29,25],[29,28],[29,38],[29,39],[29,40],[29,41],[30,10],[30,31],[30,43],[31,30],[31,44],[32,12],[32,46],[33,47],[34,35],[35,18],[35,34],[35,49],[36,17],[37,5],[37,50],[38,6],[38,29],[38,39],[39,28],[39,29],[39,38],[40,25],[40,28],[40,29],[40,41],[41,7],[41,25],[41,29],[41,40],[42,8],[42,9],[42,45],[43,10],[43,30],[44,10],[44,31],[45,4],[45,9],[45,42],[46,12],[46,32],[46,47],[47,33],[47,46],[49,35],[50,5],[50,37],[50,51],[51,50]]; Alright johnnyboy, send in some troops and let's see this bad boy in action. So I've been thinking a lot about the ramifications of our combined efforts lately. I know I mentioned potential wonkyness etc along the way, but I must say we really do have the potential to fundamentally change the game here. It's all about reliability. If we can reliably get the AI in and out (and have them resume engine-pathing upon exit), the sky becomes the new limit and suddenly we can achieve things currently unimaginable. OK that's it for now, back to secret lair.
  3. Thanks, good to know! I don't particularly need one-way connections, now or for the foreseeable future. Still curious though (after carefully reading your answer a couple of times): I understand now you support only two-way connections and that we only need to provide each connection once. <- Considering this, will we hurt performance by providing each connection twice (one per each way)? (Because in my case it's easier to build an array of connections that includes each connection both ways...) Hope that makes sense.
  4. Many thanks for this! Quick question about input parameters. Should connections list include each connection both ways? For example, if node1 is connected to node2, should connections list include just [fromID1, toID2]? Or in this case, does connections list need both [fromID1, toID2] and [fromID2, toID1]? Also, in case first choice is the correct (connections list needing just [fromID1, toID2]), if you go ahead and provide both ([fromID1, toID2] and [fromID2, toID1]), will this still work? ... And if so will it take significant performance hit?
  5. Please johnnyboy correct if I've got any of this wrong, but basically his script motors the AI around using playMove (or similar, by playing animations). Once we have a good set of usable points (which my building scanner will hopefully be able to generate), we'll apply Sarogahtyp's Simple Shortest Paths (or one of the other node path selection functions he's developing) to pick a path, and motor our AIs in and out: My ultimate goal is to assemble a giant array with the type names of all buildings in the game (including all popular mods), and have my building scanner run all night (or for days?) and capture all the important points from all those buildings. After we get all the basic points covered, I hope to include "fighting positions" so AI could potentially take up positions in a building based on the direction of the threat, etc. Btw - Froggy mentioned this quite excellent idea, thanks for that! From my perspective, johnnyboy's project is 100% worthwhile and his awesome demo videos sealed the deal getting us on board to help out. However, I would suggest keeping your expectations somewhat in check. As someone mentioned once we integrate all the parts, the whole thing might be kinda wonky, etc. My scanner will be evolving over time, and most likely won't always pick the best points. And for heaven's sake, we're using forced animations to power the AI around. Hmmm... What could possibly go wrong? Also johnnyboy is trying to figure out how to get multiple AI to operate inside a building simultaneously, but as you can imagine that will be quite a juggling act. Hoping he can pull it off!
  6. Hi all, quick update. Made good progress over the past few days (bug-fixing, refactoring, etc). Notably, I'm now caching the floor points in profileNamespace, which has sped up development considerably. News-flash, moved onto Chokepoints! To get Chokepoints, we need two critical ingredients: A good clean outline. A reliable way to get all nodes contained within the outline. Recall as of last update, our outlines were pretty good but did not line up with the stairs (so not clean). I now added a process by which the outlines clean themselves, and change shape over as many iterations as necessary to arrive at final cleaned shapes. A few snapshots of the process in action: Original (rough) outline: Detection Process (picture this happening potentially multiple times as the outline mostly shrinks & sometimes grows slightly): Final Clean outline: Now, you may be wondering: “Why have the outlines self-clean like this? What happened to dumping and rebuilding the collections?” For those curious, here’s why: Also, the cleaned outlines do a great job now on balconies and porches, by detecting those skinny rails, etc. (Note- We can't check all the collection's connections like this, as that would be prohibitively expensive CPU-wise, grinding down development of these scripts to a halt. Sticking to this increased level of detection on just the outlines is quite CPU friendly.) In the mean time, I found a way to get all the nodes inside the outline of any collection, even if it wraps up above & over itself. This is a huge breakthrough, as using inPolygon (and cutting the collections) is no longer necessary! Now we can get the Chokepoints (… well almost). So far, we have raw "chokeway" points. I’m going to have to pour over a bunch of possible chokeway point / outline arrangements and develop a good algorithm, in order to ultimately refine these raw chokeway points into usable Chokepoints. Yeah, babysteps! Raw "chokeway" points:
  7. 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.
  8. 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).
  9. 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.)
  10. @.kju Wow, that totally just blew my mind! Imagine all the possibilities.
  11. 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!
  12. "Up! Up! And Away!" "Up the Stairs... To the 2nd Floor!" It's starting to come together. Slowly...
  13. 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?)
  14. @johnnyboy Agree on all points! (Should emphasize, this is your show & master plan. Seriously, thanks for spearheading!) Wow, that sounds kick ass! Hope you can make it work.
  15. Thanks, and good question. Yes, it's pretty much all lineIntersectsSurfaces. So far, it's goes something like this: 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.) 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". 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.