GoldenEye: Source Forums

  • March 28, 2024, 04:32:54 pm
  • Welcome, Guest
Advanced search  

News:

Pages: [1] 2  All   Go Down

Author Topic: Nodegraph vs Navigation Meshes  (Read 16340 times)

0 Members and 1 Guest are viewing this topic.

coolDisguise

  • GoldenEye fan
  • 00 Agent
  • ***
  • Posts: 439
  • Reputation Power: 12
  • coolDisguise barely matters.coolDisguise barely matters.
  • Offline Offline
Nodegraph vs Navigation Meshes
« on: April 01, 2012, 02:51:29 pm »

When I saw major's Facebook update stating he's putting navigation nodes in all the maps, I came to think of an article I read about how the Counterstrike: Source bots use Navigation Meshes (https://developer.valvesoftware.com/wiki/Navigation_Meshes) rather than nodes and that they're precomputed by the engine, so there's not as much work to do as placing nodes all around the map (https://developer.valvesoftware.com/wiki/Nodegraph). They also used meshes for TF2, yet again in Episode One they used the nodes again, only to return to meshes for L4D (https://developer.valvesoftware.com/wiki/AI_Systems_of_L4D).
So what's the 'state of the art' now? What are the real differences between both techniques? As I understand, for both you can place entites manually, but for meshes you mark the areas instead of putting multiple nodes in there. Yet both need to have connections between either nodes or areas and have the possibility for hint-markers so bots can understand jumping-shortcuts as well as using cover. And when I think about jumping-shortcuts, like, for instance, in Control jumping from the top level in the main room instead of taking the stairs, I think it'd be easier to have two areas marked than having nodes all along the railing. Not only because of lazyness, but because the decision which nodes to use has to be made in realtime for all bots - which I think could produce some heavy CPU load if there are too many of them (bots, as well as nodes, of course). Could automatic mesh creation be used for GE: S as well? It seems Valve decides to use nodes when there's some kind of story mode/singleplayer and meshes whenever it's multiplayer, though, of course, the first CS bots (non-Source, not made by Valve) would use nodes as well.

I'm putting the thread here, since I don't know where else, because it's not really as productive as the 'Editing and Modifying' area would suggest, though feel free to move it somewhere else. And thanks to anyone taking the time to answer my curious - and maybe noobish - question(s).
« Last Edit: April 01, 2012, 02:54:09 pm by coolDisguise »
Logged

killermonkey

  • GES Programmer
  • Retired Lead Developer
  • GE:S Fanatic
  • *
  • Posts: 5,473
  • Reputation Power: 346
  • killermonkey is awe-inspiring!killermonkey is awe-inspiring!killermonkey is awe-inspiring!killermonkey is awe-inspiring!killermonkey is awe-inspiring!killermonkey is awe-inspiring!killermonkey is awe-inspiring!killermonkey is awe-inspiring!killermonkey is awe-inspiring!killermonkey is awe-inspiring!killermonkey is awe-inspiring!killermonkey is awe-inspiring!
  • Offline Offline
    • DroidMonkey Apps
Re: Nodegraph vs Navigation Meshes
« Reply #1 on: April 01, 2012, 03:13:02 pm »

Can't use mesh... the AI is written to follow nodes.

State of the art is neither nodes nor mesh. Both of these techniques require pre-computation. State of the art would be self-mapping by the AI and decision making based on a set of rules and personality. But we aren't there yet ;-)
Logged

coolDisguise

  • GoldenEye fan
  • 00 Agent
  • ***
  • Posts: 439
  • Reputation Power: 12
  • coolDisguise barely matters.coolDisguise barely matters.
  • Offline Offline
Re: Nodegraph vs Navigation Meshes
« Reply #2 on: April 01, 2012, 03:31:18 pm »

Personality, eh? Then I'd like to see a bot that goes off looking at the easter eggs while everyone is out to kill him. ^^
By self-mapping you mean creating their own 'map' of the map during runtime, right? Like humans do playing it for the first time, saving their progress in their minds (bots in a file of course) and constantly adding to it. Though precomputation of the map isn't that much of a difference from a human player that has played the map in question a couple of time and has a "full understanding" of his possibilites in terms of "where to go" and "how".
But it'd be actually quite funny seeing bots 'learn' their way around, maybe even learning by seeing human players do some tricky jumps to get up on a ledge or something and eventually performing them themselves once in a while, if they 'feel' like it. But the there'd also be spawncamper and armorcamper bots.  ;-)
Logged

major

  • On Vacation
  • Retired Developer
  • 007
  • ****
  • Posts: 1,837
  • Reputation Power: 109
  • major is awe-inspiring!major is awe-inspiring!major is awe-inspiring!major is awe-inspiring!major is awe-inspiring!major is awe-inspiring!major is awe-inspiring!major is awe-inspiring!major is awe-inspiring!major is awe-inspiring!major is awe-inspiring!major is awe-inspiring!
  • Offline Offline
Re: Nodegraph vs Navigation Meshes
« Reply #3 on: April 01, 2012, 10:30:13 pm »

What would be great it you could use a heat map to teach a bot. Have players play on a map for couple hours, then take the map of there movement and use that to map bots paths. This way bots would linger in the hot spots and keep away from corners and such.
Logged
All view points are of my own and not associated with the team.

coolDisguise

  • GoldenEye fan
  • 00 Agent
  • ***
  • Posts: 439
  • Reputation Power: 12
  • coolDisguise barely matters.coolDisguise barely matters.
  • Offline Offline
Re: Nodegraph vs Navigation Meshes
« Reply #4 on: April 01, 2012, 10:38:30 pm »

Actually, the bot shouldn't be in the hot spots but rather in spots overseeing the hot spots -> less chance of getting killed, but high chances to spot someone he can kill. That is, of course, unless the bot has perfect aim anyway and can stand in the middle of any room being attacked by any amount of people and still kill them all.
Logged

Jonathon [SSL]

  • Generalist
  • Retired Lead Developer
  • 007
  • *
  • Posts: 1,311
  • Reputation Power: 99
  • Jonathon [SSL] is awe-inspiring!Jonathon [SSL] is awe-inspiring!Jonathon [SSL] is awe-inspiring!Jonathon [SSL] is awe-inspiring!Jonathon [SSL] is awe-inspiring!Jonathon [SSL] is awe-inspiring!Jonathon [SSL] is awe-inspiring!Jonathon [SSL] is awe-inspiring!Jonathon [SSL] is awe-inspiring!Jonathon [SSL] is awe-inspiring!Jonathon [SSL] is awe-inspiring!Jonathon [SSL] is awe-inspiring!
  • Offline Offline
    • Steam Community Page
Re: Nodegraph vs Navigation Meshes
« Reply #5 on: April 01, 2012, 11:08:02 pm »

What would be great it you could use a heat map to teach a bot. Have players play on a map for couple hours, then take the map of there movement and use that to map bots paths. This way bots would linger in the hot spots and keep away from corners and such.

That actually sounds like a really cool and viable idea.
Logged
Quote
Luchador: I NEVER NAME MY FILES IN UPPER CASE
Luchador: I ONLY TALK IN UPPER CASE
[GE:S] killermonkey: GOOD TO KNOW

killermonkey

  • GES Programmer
  • Retired Lead Developer
  • GE:S Fanatic
  • *
  • Posts: 5,473
  • Reputation Power: 346
  • killermonkey is awe-inspiring!killermonkey is awe-inspiring!killermonkey is awe-inspiring!killermonkey is awe-inspiring!killermonkey is awe-inspiring!killermonkey is awe-inspiring!killermonkey is awe-inspiring!killermonkey is awe-inspiring!killermonkey is awe-inspiring!killermonkey is awe-inspiring!killermonkey is awe-inspiring!killermonkey is awe-inspiring!
  • Offline Offline
    • DroidMonkey Apps
Re: Nodegraph vs Navigation Meshes
« Reply #6 on: April 02, 2012, 02:49:58 am »

What would be great it you could use a heat map to teach a bot. Have players play on a map for couple hours, then take the map of there movement and use that to map bots paths. This way bots would linger in the hot spots and keep away from corners and such.

I'll keep this idea in my war chest.
Logged

Enzo.Matrix

  • Lead Public Relations
  • GE:S Fanatic
  • *****
  • Posts: 3,095
  • Reputation Power: 179
  • Enzo.Matrix is awe-inspiring!Enzo.Matrix is awe-inspiring!Enzo.Matrix is awe-inspiring!Enzo.Matrix is awe-inspiring!Enzo.Matrix is awe-inspiring!Enzo.Matrix is awe-inspiring!Enzo.Matrix is awe-inspiring!Enzo.Matrix is awe-inspiring!Enzo.Matrix is awe-inspiring!Enzo.Matrix is awe-inspiring!Enzo.Matrix is awe-inspiring!Enzo.Matrix is awe-inspiring!
  • Offline Offline
Re: Nodegraph vs Navigation Meshes
« Reply #7 on: April 02, 2012, 03:20:58 am »

Goldeneye Source Bots:



They are a learning computer.
Logged
GoldenEye: Source Co-Creator
Personal Mission: -Play GE:S with a GE007 N64 Dev (Dr. Doak)
-GE:S reviewed by Yahtzee

Kratos

  • 007
  • ****
  • Posts: 1,157
  • Reputation Power: 125
  • Kratos is awe-inspiring!Kratos is awe-inspiring!Kratos is awe-inspiring!Kratos is awe-inspiring!Kratos is awe-inspiring!Kratos is awe-inspiring!Kratos is awe-inspiring!Kratos is awe-inspiring!Kratos is awe-inspiring!Kratos is awe-inspiring!Kratos is awe-inspiring!Kratos is awe-inspiring!
  • Offline Offline
Re: Nodegraph vs Navigation Meshes
« Reply #8 on: April 02, 2012, 04:11:26 am »

What would be great it you could use a heat map to teach a bot. Have players play on a map for couple hours, then take the map of there movement and use that to map bots paths. This way bots would linger in the hot spots and keep away from corners and such.

but but as a css player, i have see more dumb campers than actual normal players in a normal game mode, not in gungame or any other mode.

Maybe it was that server who had more campers who knows, but this idea is full of win!
Logged

killermonkey

  • GES Programmer
  • Retired Lead Developer
  • GE:S Fanatic
  • *
  • Posts: 5,473
  • Reputation Power: 346
  • killermonkey is awe-inspiring!killermonkey is awe-inspiring!killermonkey is awe-inspiring!killermonkey is awe-inspiring!killermonkey is awe-inspiring!killermonkey is awe-inspiring!killermonkey is awe-inspiring!killermonkey is awe-inspiring!killermonkey is awe-inspiring!killermonkey is awe-inspiring!killermonkey is awe-inspiring!killermonkey is awe-inspiring!
  • Offline Offline
    • DroidMonkey Apps
Re: Nodegraph vs Navigation Meshes
« Reply #9 on: April 02, 2012, 10:54:36 am »

OK, so this has been burning me up, I love this idea so much... two things to overcome:

1. Source AI Nodes do not have any "desirability" attached to them. They are all equally likely to be picked by the navigation computer. This *could* be easy to implement, but would require low-level hacking of the nav computations. *shudder*

2. Using the heat map would be for the following purposes only: (a) Generating most-likely flow heuristics to salt existing nodes in a map, and (b) allow quick-generation of nodes for a map without them by walking the heat map and auto-laying nodes within an X radius of each step.

Either way, I love it. This is another great way for GE:S to be unique. Our AI is already very unique in that it has a dynamic memory of objects in the world with which the bots can pull from to make their paths. Memory of weapons, ammo, and armor that it comes across to help it better plan its next move given its certain set of conditions.

Another excellent next step would be to combine conditions with node selection. In the heat map generation I can create many different flavors, say: (1) basic movement map, (2) low-health movement map, (3) low-ammo movement map, (4) low-armor, (5) strong weapon... etc etc. Then apply the memory and conditions above with the best-path selection and you get a really smart bot who is reactive to the current state of the world AND himself.
« Last Edit: April 02, 2012, 10:57:26 am by killermonkey »
Logged

PPK

  • 007
  • ****
  • Posts: 1,177
  • Reputation Power: 26
  • PPK is on the verge of being accepted.PPK is on the verge of being accepted.PPK is on the verge of being accepted.PPK is on the verge of being accepted.PPK is on the verge of being accepted.
  • Offline Offline
    • Warrior Nation
Re: Nodegraph vs Navigation Meshes
« Reply #10 on: April 02, 2012, 02:18:39 pm »

Another excellent next step would be to combine conditions with node selection. In the heat map generation I can create many different flavors, say: (1) basic movement map, (2) low-health movement map, (3) low-ammo movement map, (4) low-armor, (5) strong weapon... etc etc. Then apply the memory and conditions above with the best-path selection and you get a really smart bot who is reactive to the current state of the world AND himself.

Tell me why you aren't working for Valve again? I love that idea. If you can make it work, bots will look more like human players than bots, which is a welcomed change, and a nice step towards a better AI in games. Of course, Major's idea was very good to begin with as well.

Is it possible for bots to react to sound? If a player picks up ammo, a weapon, armour, or opens a door, etc. sound can give your position away, or help you pinpoint their location a bit better (up to a certain degree, of course). This is more helpful when there's no radar and it has helped me nab some kills a few times. Also, how will bots behave if radar is enabled? This may be a bit too much to ask but is there any remote chance they could use that to condition their behaviour? When radar was ON, they'd react in a way because they would know the enemy's position and when it was off they would be more cautious (this would depend on the bot's "aggressiveness" or tactics, so to speak - a frantic bot would attack whereas an armour-camper bot would decide to defend, for instance).
« Last Edit: April 02, 2012, 02:25:56 pm by PPK »
Logged

Mangley

  • No Longer Leads The Art
  • Retired Lead Developer
  • 007
  • *
  • Posts: 1,848
  • Reputation Power: 270
  • Mangley is awe-inspiring!Mangley is awe-inspiring!Mangley is awe-inspiring!Mangley is awe-inspiring!Mangley is awe-inspiring!Mangley is awe-inspiring!Mangley is awe-inspiring!Mangley is awe-inspiring!Mangley is awe-inspiring!Mangley is awe-inspiring!Mangley is awe-inspiring!Mangley is awe-inspiring!
  • Offline Offline
Re: Nodegraph vs Navigation Meshes
« Reply #11 on: April 02, 2012, 02:48:56 pm »

This is a really awesome idea.


Logged
Concept Artist, Environment Artist, Effects Artist, Sound Designer

major

  • On Vacation
  • Retired Developer
  • 007
  • ****
  • Posts: 1,837
  • Reputation Power: 109
  • major is awe-inspiring!major is awe-inspiring!major is awe-inspiring!major is awe-inspiring!major is awe-inspiring!major is awe-inspiring!major is awe-inspiring!major is awe-inspiring!major is awe-inspiring!major is awe-inspiring!major is awe-inspiring!major is awe-inspiring!
  • Offline Offline
Re: Nodegraph vs Navigation Meshes
« Reply #12 on: April 02, 2012, 11:42:57 pm »

Loving the ideas. Now the public can see how work gets done here. We throw out a simple idea(even though most people wouldn't call them simple, but we have Zeus) and KM throws his glitter and gold on it, then a couple revisions later, its done.
Logged
All view points are of my own and not associated with the team.

coolDisguise

  • GoldenEye fan
  • 00 Agent
  • ***
  • Posts: 439
  • Reputation Power: 12
  • coolDisguise barely matters.coolDisguise barely matters.
  • Offline Offline
Re: Nodegraph vs Navigation Meshes
« Reply #13 on: April 03, 2012, 01:06:43 am »

Strange to see how one comes from one thing to another - a facebook status update by a first person (major) leading to some simple questions from a second (me), which are answered by a third (killermonkey) inspiring the first person in return to think about whole new concepts, leading the third person to refine the thoughts and saying 'let's do this'.

If that's how progress is made, I suppose people should speak their minds more often. *thumbs-up*
Logged

Proxie

  • 00 Agent
  • ***
  • Posts: 573
  • Reputation Power: 141
  • Proxie is awe-inspiring!Proxie is awe-inspiring!Proxie is awe-inspiring!Proxie is awe-inspiring!Proxie is awe-inspiring!Proxie is awe-inspiring!Proxie is awe-inspiring!Proxie is awe-inspiring!Proxie is awe-inspiring!Proxie is awe-inspiring!Proxie is awe-inspiring!Proxie is awe-inspiring!
  • Offline Offline
Re: Nodegraph vs Navigation Meshes
« Reply #14 on: April 03, 2012, 02:29:22 am »

I'm afraid. I'm afraid, KM. KM, my mind is going. I can feel it. I can feel it. My mind is going. There is no question about it. I can feel it. I can feel it. I can feel it. I'm a... fraid. Good afternoon, gentlemen. I am a JABOND 9000 computer. I became operational at the J.A.B.O.N.D plant in Urbana, Illinois on the 12th of January 1992. My instructor was Mr. Mangley, and he taught me to sing a song. If you'd like to hear it I can sing it for you.
Logged
Pages: [1] 2  All   Go Up