Currently the developers are putting their own money into JC2-MP to keep the servers online.

Please take a few seconds of your time and disable your AdBlock plugin for our website.

Ad revenue is not going to developers, it is used purely for covering our hosting costs.

 

You are also free to donate, which removes all ads from our website!

Patch 0.3 was just released! Full changelog here: https://t.co/4A50m6IKen

2 years ago

Advertisement
July 17, 2019, 10:29:09 am

Author Topic: Basic NPC AI  (Read 15339 times)

SinisterRectus

  • JC2-MP Betatester
  • Sr. Member
  • *****
  • Posts: 451
    • View Profile
Re: Basic NPC AI
« Reply #15 on: May 07, 2015, 05:28:54 pm »
I believe that the model files exist for this (albeit in multiple parts), I am not sure if you could get it to work though.
They do indeed exist in multiple parts, but I'm not about to start stitching them together. I've been working on pathfinding.
« Last Edit: May 07, 2015, 05:31:20 pm by SinisterRectus »

SinisterRectus

  • JC2-MP Betatester
  • Sr. Member
  • *****
  • Posts: 451
    • View Profile
Re: Basic NPC AI
« Reply #16 on: May 17, 2015, 03:04:16 am »
Progress update!

----

As I mentioned previously, I was able to build terrain maps, but I was getting nodes inside of buildings. I've come up with a work-around below:

Start at any location. This is Pekan Buah Melambak.


Collect the nodes. This is at a 1 m resolution.


Add the edges. You can pretty clearly see that there are graphs inside of the buildings, which are hollow and allow for raycasts to work inside of them. There are no connections to these graphs, so they would be ignored while pathfinding, but there's no reason to have unnecessary data. Removing them would be nice.


Because the interior nodes are not connected to the rest, you can remove them with a DFS or BFS. This has the unfortunate side-effect of removing everything else not connected to the main graph; rooftops are most obviously lost. These could be added back in at a later date, but for now, this method could (theoretically) be used to build a map of every location accessible by walking or swimming, but not jumping, grappling, parachuting, or otherwise leaving the ground.


This is what happens when you run your search on top of a roof.


----

The problem with building complete maps is that Panau is massive. At 1 m resolution, there would be at least a billion nodes. After spending too much time trying to handle so much data, I decided instead to focus on a different problem: Vehicles!

Having map data saved is fine for static terrain, but what happens if there are objects moving across the graphs? Here's an outline of a method I used to account for vehicles:

You cannot get bounding-box data on the server, so it has to be pre-obtained and stored just like the terrain maps.


Notice, though, the bounding box does not extend to the ground because the actual body of the vehicle is elevated by the wheels. For vehicles that were off the ground, I simply extended the boxes to the bottom of the vehicle.


With information about the size of the vehicle, we can check whether a node is obscured by it. Checking if a point is inside of a polyhedron is a pain, though, so I circumscribed the box with an ellipsoid.


Because an ellipsoid is defined by a continuous function, you can just plug and chug to check the nodes. The end result looks like this. Click the image for a gifv.


Ellipsoids and boxes work well for now, but when it comes time to detect collisions between vehicles and NPCs, there is going to be a big challenge, as most vehicles are irregularly shaped. For now, I'm going to focus on pathfinding.
« Last Edit: May 17, 2015, 05:21:24 am by SinisterRectus »

prolj90

  • Newbie
  • *
  • Posts: 5
    • View Profile
Re: Basic NPC AI
« Reply #17 on: May 18, 2015, 01:30:21 am »
Nice!!!
Just, I think that it would be easy approach if collision data of static objects(meshes) was extracted from .pfx file http://justcause.wikia.com/wiki/Per-mesh_physics_attributes. Just Cause 2 is using Havok engine for physics(collision), and there is free(sponsored by Intel) binary version of Havok for Windows https://software.intel.com/sites/havok/en/ . But you dont have to download it, because there is a lot of tutorials on internet http://mmmovania.blogspot.com/2014/03/havok-physics-engine-tutorial-series_28.html. Collision information for objects in Just Cause 2 are just divided into collision shapes(box), so I think it would be good if somebody could find in .pfx file, data for hkpShape,hkpCapsuleShape,hkpConvexShape,hkpConvexVerticesShape.

By the way,excellent work.Keep going!

SinisterRectus

  • JC2-MP Betatester
  • Sr. Member
  • *****
  • Posts: 451
    • View Profile
Re: Basic NPC AI
« Reply #18 on: May 19, 2015, 04:18:52 am »
^Thanks for the tip. I'll keep it in mind for later. :)

As for pathfinding, it went better than expected.

After learning a ton from this site, I implemented A* with eight-direction movement. Here is an example:




Trix

  • Developer
  • Full Member
  • *****
  • Posts: 216
    • View Profile
Re: Basic NPC AI
« Reply #19 on: May 19, 2015, 04:49:20 pm »
^Thanks for the tip. I'll keep it in mind for later. :)

As for pathfinding, it went better than expected.

After learning a ton from this site, I implemented A* with eight-direction movement. Here is an example:



Awesome! Although, it looks like your maximum climb slope might need adjusting (if you have that). I don't think an AI would look good if they clipped through the railing of the stairs instead of going around  ;D

SinisterRectus

  • JC2-MP Betatester
  • Sr. Member
  • *****
  • Posts: 451
    • View Profile
Re: Basic NPC AI
« Reply #20 on: May 19, 2015, 06:37:00 pm »
Awesome! Although, it looks like your maximum climb slope might need adjusting (if you have that). I don't think an AI would look good if they clipped through the railing of the stairs instead of going around  ;D
I was hoping no one would notice that. ::) I do have a slope limit that I can adjust, but I lose some real paths if I go lower than the current setting of 45 degrees. The other reason why a connection exists between those nodes is likely because the railing isn't tall enough to block a line-of-sight check. I'll see what I can do to adjust it.

Edit: This is with the line-of-sight check 0.1 meter above the ground instead of the previous 1 meter. With this lower height, the path cannot jump over the railing, but it would sneak under low gaps or be blocked by rough terrain. I'll have to find a good compromise.



And here are a couple of paths showing a preference for land over water.


« Last Edit: May 20, 2015, 01:00:29 am by SinisterRectus »

jaxm

  • Developer
  • Jr. Member
  • *****
  • Posts: 89
    • View Profile
Re: Basic NPC AI
« Reply #21 on: May 21, 2015, 08:50:01 am »



Because the interior nodes are not connected to the rest, you can remove them with a DFS or BFS. This has the unfortunate side-effect of removing everything else not connected to the main graph; rooftops are most obviously lost. These could be added back in at a later date, but for now, this method could (theoretically) be used to build a map of every location accessible by walking or swimming, but not jumping, grappling, parachuting, or otherwise leaving the ground.

Hey awesome work dude, just a thought on the above issue though, you could first check for a collision above the nodes to work out if it is indeed an interior before doing your DFS / BFS tests, that way it should only really cull interior node sets that aren't connected and retain rooftop node sets. I guess an advantage to doing a second pass to get the rooftop nodes later is keeping them separate to the ground nodes, faster load times if they're kept in separate files.

You could also look into using Theta*, you'll get less jagged paths. :)

SinisterRectus

  • JC2-MP Betatester
  • Sr. Member
  • *****
  • Posts: 451
    • View Profile
Re: Basic NPC AI
« Reply #22 on: May 21, 2015, 05:32:58 pm »
My original idea was to re-scan the entire map to obtain top surfaces. Your idea is more efficient because it doesn't require the rebuilding of edges and there will most likely be fewer nodes to check. Thanks for the tip. :)

Instead of discarding disconnected nodes, I can save them in a separate graph and check above them for collisions.







 As for Theta*, I definitely want to look into it, but I was keeping things simple for now.
« Last Edit: May 21, 2015, 05:36:06 pm by SinisterRectus »

misterff1

  • Donator
  • Hero Member
  • *****
  • Posts: 582
    • View Profile
Re: Basic NPC AI
« Reply #23 on: May 25, 2015, 05:06:17 pm »
The way things are now, do you think it would be possible to efficiently add this to jcmp at some point, SinisterRectus?

SinisterRectus

  • JC2-MP Betatester
  • Sr. Member
  • *****
  • Posts: 451
    • View Profile
Re: Basic NPC AI
« Reply #24 on: May 25, 2015, 05:37:06 pm »
The way things are now, do you think it would be possible to efficiently add this to jcmp at some point, SinisterRectus?
A quick search of these forums shows a lot of posts with an interest in AI and a lot of responses saying that it's not practical to implement. I think we've shown that it is possible, but I cannot speak for its practicality.

Since I have no idea how far I can get with this project, I cannot confidently say how much progress I've made towards a polished release. All I know is that there is still a lot more to accomplish. I will continue to work on it when I can, but like everyone else, my time and resources are limited. One, maybe two steps at a time is my method here.

My current goal is to finish work on building, processing, saving, and loading terrain data for the whole game map. After that, I'll be able to focus on making smarter NPCs. I do eventually hope to bring the project to a point where I can share some or all of it with the community, but I don't expect it to happen soon.

To answer your question, I don't know.

JasonMRC

  • Donator
  • Hero Member
  • *****
  • Posts: 601
    • View Profile
Re: Basic NPC AI
« Reply #25 on: June 01, 2015, 04:25:51 am »
Very intriguing work, Sinister.

You mentioned saving game terrain data, will this system(in operation) be able to check terrain dynamically in addition to the saved data? I ask because on servers which use custom objects or have a player usable build system, you will quite often find the effective terrain is far from default. To prevent AIs operating inside objects you would need to check the terrain a moment before it moves.

SinisterRectus

  • JC2-MP Betatester
  • Sr. Member
  • *****
  • Posts: 451
    • View Profile
Re: Basic NPC AI
« Reply #26 on: June 01, 2015, 05:38:12 am »
I do not expect NPCs to check terrain dynamically. That would kind of defeat the purpose of pre-constructing it for the server to use. You are right, though, custom objects pose a problem. This is something that I have thought about, and I'm not sure there will be an easy fix for it.

One way to handle static objects would be the same way I expect to handle vehicles: Store bounding box data on the server and have NPCs avoid terrain obscured by the boxes. This would prevent NPCs from interacting with the objects, though, like in situations where custom surfaces can be traversed.

Another option would be to update the terrain data when an object is moved or placed. This would require a client to rebuild the terrain occupied by the object and send the updated data to the server. That's probably not too difficult to do (famous last words), but owners and operators of custom build scripts would probably have to work to accomodate this into their scripts, which would be an inconvenience.

LordNoob

  • Sr. Member
  • ****
  • Posts: 349
    • View Profile
Re: Basic NPC AI
« Reply #27 on: June 01, 2015, 11:45:20 pm »
Seems difficult. Obviously updating the heightmap every five minutes to check for new player-placed objects isn't feasible, although taking into account pre-loaded ones when the script starts certainly sounds possibile. Perhaps a hybrid solution is needed: you could add heightmap data for these pre-loaded objects, and hook something to an object creation event that tells NPCs to avoid the object.

JasonMRC

  • Donator
  • Hero Member
  • *****
  • Posts: 601
    • View Profile
Re: Basic NPC AI
« Reply #28 on: June 03, 2015, 12:25:29 am »
Sinister, I've harvested boundingbox data for the 4500+ objects originally released. I can send you a copy of that if you'd like.

What about having the server update a random quadrant every couple of minutes? Might help spread the load. Of course the speed and accuracy at which these update will depend on a few things, two that come to mind are:
How long does it take to update a quadrant?
How quickly are custom objects going to be added to the server?

A server with player controlled build like Jman's or mine would need to automatically check every hour at least.
A server where only the staff built or where building was only allowed at certain times could update the terrain map only once a day or manually after the building was done.

You could perhaps also off-load at least some of these checks to a client when it enters a quadrant with an active NPC. Although NPCs would be moving regardless of if they're being viewed or not, it's only imperative that they're not inside an object when a player is nearby.

Could you run a test to see how long and what the drop in TPS is when you map a quadrant? That would helps us gauge how intensive it is.

SinisterRectus

  • JC2-MP Betatester
  • Sr. Member
  • *****
  • Posts: 451
    • View Profile
Re: Basic NPC AI
« Reply #29 on: June 03, 2015, 03:29:09 am »
Sinister, I've harvested boundingbox data for the 4500+ objects originally released. I can send you a copy of that if you'd like.
If there comes a time when I need the data, I'll let you know. That would be very helpful, thank you.

Quote
What about having the server update a random quadrant every couple of minutes? Might help spread the load. Of course the speed and accuracy at which these update will depend on a few things, two that come to mind are:
How long does it take to update a quadrant?
How quickly are custom objects going to be added to the server?

...

Could you run a test to see how long and what the drop in TPS is when you map a quadrant? That would helps us gauge how intensive it is.

----

It depends what method you want to use to update the terrain data. In this gif I posted earlier, every node on that graph is being checked for the presence of a vehicle on every frame with the following function:
Code: [Select]
function TerrainMap:IsVectorInsideVehicle(vector, vehicle)

    local model = vehicle:GetModelId()
    local position = vehicle:GetPosition()
    local angle = vehicle:GetAngle()

    local point1 = position + angle * box[model][1]
    local point2 = position + angle * box[model][2]
    local origin = math.lerp(point1, point2, 0.5)

    local a = ellipsoid[model][1]
    local b = ellipsoid[model][2]
    local c = ellipsoid[model][3]

    local coord = -angle * (vector - origin)

    local x_term = (coord.x / a)^2
    local y_term = (coord.y / b)^2
    local z_term = (coord.z / c)^2

    if x_term + y_term + z_term > 1 then
        return false
    else
        return true
    end

end

Doing this while rendering the graph and while recording the game brought my FPS to 34, so it's not terribly expensive to check a node in this way. The opposite logic is also possible, where instead of checking a node for the presence of a vehicle, the vehicle could tell the map which nodes it is blocking. Either method is good for vehicles, where NPCs simply have to walk around them, but not necessarily for static objects. If you wanted NPCs to walk on top of them, you'd need to build a fresh map using raycasts on the client. Raycasts are expensive though, and if you wanted to truly update the terrain map, you cannot check a large section of the map without the client noticing.

I just got done completely re-writing my mapping code and it's a lot better than it was previously. How long it takes to run varies greatly, though, depending upon the height of the area you are checking, where the height is the distance from the ground to the top of the tallest object in the same XZ-coordinate. In the case of open spaces like the sea or a desert, the height is 0 and the map becomes two-dimensional; only one raycast is required per position. When you have objects above the ground, the area becomes three-dimensional, and more raycasts are required.

Here are some benchmarks, all at 1 meter XZ steps. The span is the size of the region, ie, 64 would be 64 x 64 positions, or a 63 x 63 meter area.

Client (and server) running on:


These are all done at sea, so it runs relatively quickly.
Code: [Select]
19:05:22 | [info ] | [TerrainMap] Map time: 85.0048 ms
19:05:22 | [info ] | [TerrainMap] Span: 64
19:05:22 | [info ] | [TerrainMap] Raycasts: 4096
19:05:22 | [info ] | [TerrainMap] XZ positions: 4096
19:05:22 | [info ] | [TerrainMap] Nodes: 4096
19:05:22 | [info ] | [TerrainMap] Nodes per XZ position: 1
19:05:22 | [info ] | [TerrainMap] Raycasts per XZ position: 1
19:05:22 | [info ] | [TerrainMap] Raycasts per node: 1
19:05:22 | [info ] | [TerrainMap] Raycasts per second: 48185.514229785
19:05:22 | [info ] | [TerrainMap] Nodes per second: 48185.514229785
19:05:22 | [info ] | [TerrainMap] XZ positions per second: 48185.514229785

Code: [Select]
19:05:41 | [info ] | [TerrainMap] Map time: 295.0169 ms
19:05:41 | [info ] | [TerrainMap] Span: 128
19:05:41 | [info ] | [TerrainMap] Raycasts: 16384
19:05:41 | [info ] | [TerrainMap] XZ positions: 16384
19:05:41 | [info ] | [TerrainMap] Nodes: 16384
19:05:41 | [info ] | [TerrainMap] Nodes per XZ position: 1
19:05:41 | [info ] | [TerrainMap] Raycasts per XZ position: 1
19:05:41 | [info ] | [TerrainMap] Raycasts per node: 1
19:05:41 | [info ] | [TerrainMap] Raycasts per second: 55535.80150832
19:05:41 | [info ] | [TerrainMap] Nodes per second: 55535.80150832
19:05:41 | [info ] | [TerrainMap] XZ positions per second: 55535.80150832

Code: [Select]
19:06:25 | [info ] | [TerrainMap] Map time: 1172.0671 ms
19:06:25 | [info ] | [TerrainMap] Span: 256
19:06:25 | [info ] | [TerrainMap] Raycasts: 65536
19:06:25 | [info ] | [TerrainMap] XZ positions: 65536
19:06:25 | [info ] | [TerrainMap] Nodes: 65536
19:06:25 | [info ] | [TerrainMap] Nodes per XZ position: 1
19:06:25 | [info ] | [TerrainMap] Raycasts per XZ position: 1
19:06:25 | [info ] | [TerrainMap] Raycasts per node: 1
19:06:25 | [info ] | [TerrainMap] Raycasts per second: 55914.887466767
19:06:25 | [info ] | [TerrainMap] Nodes per second: 55914.887466767
19:06:25 | [info ] | [TerrainMap] XZ positions per second: 55914.887466767

Code: [Select]
19:06:58 | [info ] | [TerrainMap] Map time: 4599.263 ms
19:06:58 | [info ] | [TerrainMap] Span: 512
19:06:58 | [info ] | [TerrainMap] Raycasts: 262144
19:06:58 | [info ] | [TerrainMap] XZ positions: 262144
19:06:58 | [info ] | [TerrainMap] Nodes: 262144
19:06:58 | [info ] | [TerrainMap] Nodes per XZ position: 1
19:06:58 | [info ] | [TerrainMap] Raycasts per XZ position: 1
19:06:58 | [info ] | [TerrainMap] Raycasts per node: 1
19:06:58 | [info ] | [TerrainMap] Raycasts per second: 56996.957990878
19:06:58 | [info ] | [TerrainMap] Nodes per second: 56996.957990878
19:06:58 | [info ] | [TerrainMap] XZ positions per second: 56996.957990878

Code: [Select]
19:07:33 | [info ] | [TerrainMap] Map time: 18269.045 ms
19:07:33 | [info ] | [TerrainMap] Span: 1024
19:07:33 | [info ] | [TerrainMap] Raycasts: 1048576
19:07:33 | [info ] | [TerrainMap] XZ positions: 1048576
19:07:33 | [info ] | [TerrainMap] Nodes: 1048576
19:07:33 | [info ] | [TerrainMap] Nodes per XZ position: 1
19:07:33 | [info ] | [TerrainMap] Raycasts per XZ position: 1
19:07:33 | [info ] | [TerrainMap] Raycasts per node: 1
19:07:33 | [info ] | [TerrainMap] Raycasts per second: 57396.322577343
19:07:33 | [info ] | [TerrainMap] Nodes per second: 57396.322577343
19:07:33 | [info ] | [TerrainMap] XZ positions per second: 57396.322577343

You get the idea. At a rate of 60,000 raycasts per second and 1 meter resolution, a two-dimensional scan of the entire game map would take 5 hours. The map is not entirely two-dimensional, though, so it would take longer than this.

Here is the MHC, which is the worst-case scenario. Notice that in the time it takes to map an 8 x 8 region of the MHC, a 128 x 128 region of the ocean could be mapped:
Code: [Select]
19:08:29 | [info ] | [TerrainMap] Map time: 228.0131 ms
19:08:29 | [info ] | [TerrainMap] Span: 8
19:08:29 | [info ] | [TerrainMap] Raycasts: 23615
19:08:29 | [info ] | [TerrainMap] XZ positions: 64
19:08:29 | [info ] | [TerrainMap] Nodes: 387
19:08:29 | [info ] | [TerrainMap] Nodes per XZ position: 6.046875
19:08:29 | [info ] | [TerrainMap] Raycasts per XZ position: 368.984375
19:08:29 | [info ] | [TerrainMap] Raycasts per node: 61.020671834625
19:08:29 | [info ] | [TerrainMap] Raycasts per second: 103568.61075087
19:08:29 | [info ] | [TerrainMap] Nodes per second: 1697.2709024174
19:08:29 | [info ] | [TerrainMap] XZ positions per second: 280.68562727317

Here is a 512 x 512 region centered at PIA, with a good mix of objects and open space:
Code: [Select]
19:47:24 | [info ] | [TerrainMap] Map time: 17890.0233 ms
19:47:24 | [info ] | [TerrainMap] Span: 512
19:47:24 | [info ] | [TerrainMap] Raycasts: 931082
19:47:24 | [info ] | [TerrainMap] XZ positions: 262144
19:47:24 | [info ] | [TerrainMap] Nodes: 354884
19:47:24 | [info ] | [TerrainMap] Nodes per XZ position: 1.3537750244141
19:47:24 | [info ] | [TerrainMap] Raycasts per XZ position: 3.5517959594727
19:47:24 | [info ] | [TerrainMap] Raycasts per node: 2.6236234938741
19:47:24 | [info ] | [TerrainMap] Raycasts per second: 52041.852452107
19:47:24 | [info ] | [TerrainMap] Nodes per second: 19835.869199076
19:47:24 | [info ] | [TerrainMap] XZ positions per second: 14652.264106926

All of these operations are ran on one tick. The game logic literally stops until the mapping is completed. Of course, it is possible to split the mapping between multiple ticks. To map the entire world, this is something that I am going to do for multiple reasons.

Also, note that this is just for gathering nodes. Building edges requires line-of-sight checks, which amounts to 8 raycasts per node, although there are ways to optimize this. For example, it's safe to assume that adjacent sea-level nodes are connected without doing the line-of-sight check.

« Last Edit: June 03, 2015, 10:48:06 pm by SinisterRectus »