Sign in to follow this  
WombatTurkey

How to handle Monster AI w/ Player Positioning?

Recommended Posts

I guess this could go into the Monster AI sub, but not sure,

 

Long story short, I have a web browser based game similar to Diablo 2. Everything is server-side and synced with nodejs using websockets.

 

The game is instanced based and every time a player moves, their position is updated and sent to everyone in that current game (real time).

 

Here is a simple dev screen to show what I'm trying to talk about:

d001ca1b1e6586c200df241794f702f5.gif

 

 

That monster is piped from the gameserver into this users game.  I am at the point where I can run a global game loop that runs every 1.3 seconds and check if the monster is next to the player (to start attacking it), but that's boring! I want monster AI where the mob moves around and attacks the player.

 

I can obviously do that client side within JavaScript. But, my problem is how do I do that serverside? For example, if the monster starts to agro towards the player, there is no way my server can handle every single request of that monster moving to validate it. It would be thousands of requests.  There has to be some type of Monster / Client Prediction right? That's where I'm stuck.  Not looking for code, just some design philosophy insights.

Edited by WombatTurkey

Share this post


Link to post
Share on other sites

SIMSpace used client server with lockstep. but only state changes were transmitted. during steady state, a "packet" was just 23 bytes of data including header and error correction. worst was adding a new target at about 2500 bytes of data. since the game was designed with maximum randomness, combat results were transmitted, as opposed to just transmitting attacks. so the results of a player firing lasers would be resolved on the client side (including dice rolls), then the results would be sent to the server - and vica versa for hostiles controlled by the server. hostile attacks, including dice rolls, were resolved on the server, then the results were transmitted to clients. for movement, once a "target" had a heading and speed, only changes in course and heading need to be transmitted. otherwise you can just send "no change", and the client or server can use the current course and speed to update the target's position in their copy of the game world. with prediction, basically you don't wait for a "no change" packet, and assume "no change" and do your update. when the packet does finally arrive, if its not what you expected, you have to "warp" (IE teleport) the player to the correct position, or do some sort of tweening catch-up algo so they get back in sync within a few seconds. Back when I was doing Multiplayer SIMSpace, ping times were so abysmal, i decided to stick with lockstep, rather than deal with mis-prediction all the time.  I also created my own proprietary protocall. it was so robust, you could unplug the phone line, plug it back in ,and the game would keep right on running like nothing happened.

Edited by Norman Barrows

Share this post


Link to post
Share on other sites

First, you shouldn't path for enemies that are far away from players (like, way beyond the screen range). Next, you need to share  movement information between clients instead of recalculating it for each user's session. You calculate the movement, and send that to each client within range. You shouldn't be getting thousands of re-validations for movement unless you have thousands of monsters interacting with players.

Share this post


Link to post
Share on other sites
There are two main topologies you can do here:

1) Server authority. This requires the server to simulate each entity. This means you need more servers per player. That being said -- most MMO games have hundres of players and monsters per server instance, so don't automatically write that off. Also, with Node, because it's single-threaded, you will have to run multiple sharded/parallel servers in multiple processes on the same machine to make full use of the hardware.

2) Peer-to-peer. Here, perhaps some player "hosts" the game, and is the "server" from point of view of making decisions, but your "server hardware" is used to send messages between clients that may not otherwise be able to easily message each other. Just flinging packets back and forth is not particularly high load on server hardware, so it's cheaper for you, but it also means that whatever client is made/elected "host" may be able to cheat. That may or may not matter to your game design.

Share this post


Link to post
Share on other sites

It sounds to me that you're talking about how to send updates for many hundreds of enemies at once per player.

 

Rethink it and do it like rts games do.

 

Read this for inspiration: http://www.gamasutra.com/view/feature/131503/1500_archers_on_a_288_network_.php

 

Good luck! 

Share this post


Link to post
Share on other sites

Rethink it and do it like rts games do.


Deterministic lockstep simulation is a great way to do low-bandwidth networking.

It does come with some drawbacks, though:

1) All clients must use the exact same computation model. This has been a problem even for Windows, as some Pentium systems had the division bug, and some AMD FPUs do internal precision/rounding differently from Intel FPUs. Early SSE also had not-entirely-bit-precise specifications.
Assuming that all web browsers will be bit precise for floating point math and marshaling/demarshaling is probably not safe.

2) Late joins / drop-ins is much harder to implement, and will almost always require that all the other players pause for a little while the new player enters the simulation. (With extreme care, that can be avoided, but that's a LOT of work!)

Share this post


Link to post
Share on other sites

Why update hundreds of enemies when there are only a few onscreen?

Only update what can be seen by the player, this also prevents some cheating.

 

From what I remember of diabolo 2 you could be involved in battles where hundreds of monsters were on screen at once. Perhaps flocking and crowd behaviour is best for that approach with some sort of cooperative pathfinding... 

Share this post


Link to post
Share on other sites

Thanks everyone for the responses. I do only update the monsters when a player is in range and currently do what @SeanMiddleditch said using a AI ticker.

 

I cannot do the peer to peer topology as I'm using Websockets (Browser based).  But I wish I could.

 

To iterate a bit about my problem, I just don't know how to track the monster movements.

 

For example, if a player get's in range of a mob (The global Monster AI ticker will detect this on the server and start dealing damage to the player).  (Runs every 1300 ms)

 

But, how do I go about having the monster inch its way closer and closer to the player? (agro) If I want the server to be authoritative the ticker would have to be running  almost instantly and as @hplus said running that would eat up nodes resources quite fast. Especially when there's more than 1 game open. Would that be the only way? That's why I'm kind of looking for monster AI prediction / movement but somehow synced with node? I mean, when a player uses a skill I check for cooldowns, and the distance to a monster server-side to prevent naughty stuff, but just not sure how to make the server authoritative to track monster movements and AI.  I'm a bit lost, but that's kind of where I'm coming from, I'll take a look at the archers link.

Edited by WombatTurkey

Share this post


Link to post
Share on other sites

I cannot do the peer to peer topology as I'm using Websockets (Browser based). But I wish I could.


You can have a logical peer to peer topology (one player "hosts" the game instance) while you still use a physical start topology (a single server repeats messages to other players in the same session.)

how do I go about having the monster inch its way closer and closer to the player?


Then you need to have monsters ative when they're close enough that they should know where the player is to start moving towards it.

not sure how to make the server authoritative to track monster movements and AI


Just make it authoritative. If it runs too slow, first look for options to optimize the implemented code, and only when you can't do that anymore, split your world across multiple processes (cores.) I think you over-estimate the "cost" of running simulations on server side. As long as you don't add too much unnecessary indirection or repeated re-processing, you can push a lot of load even on a medium-capable modern CPU.

Share this post


Link to post
Share on other sites

First, you shouldn't path for enemies that are far away from players

 

SIMSpace kept the total number of active targets (both within and beyond visual range) in the simulation  low at all times, perhaps 20-30 at most at once.

 

 

 


2) Peer-to-peer. Here, perhaps some player "hosts" the game, and is the "server" from point of view of making decisions

 

this is how SIMSpace worked

 

 

 

 


1) All clients must use the exact same computation model. This has been a problem even for Windows, as some Pentium systems had the division bug, and some AMD FPUs do internal precision/rounding differently from Intel FPUs. Early SSE also had not-entirely-bit-precise specifications.

 

this is why SIMSpace transmitted combat results, not just attacks. due to the "maximum randomness" design of the game, different targets required different dice rolls at different times, so there was no hope of keeping the rand() functions sync'ed.  The pentium divsion bug and AMD rounding issue were not accounted for. SSE instructions were not used, and may not have existed at that time (MMX was the latest and greatest at the time as i recall).

 

 

 


2) Late joins / drop-ins is much harder to implement, and will almost always require that all the other players pause for a little while the new player enters the simulation

 

the 2500 byte setup packet to add a new target in SIMSpace did cause a pause of a couple seconds. The testers decided it was acceptable.

 


Just make it authoritative. If it runs too slow, first look for options to optimize the implemented code, and only when you can't do that anymore, split your world across multiple processes (cores.)

 

SIMSpace was 2 player co-op via modem or null-modem cable. as i recall, i estimated you needed one PC server, one PC for each player, and one PC for every ten active targets to reproduce the full single player experience in a true multiplayer environment. as best as i can figure, this was with 486/66 PCs (IE 486DX2 processor running at 66Mhz clock speed). contrast that to the dual core e300 1.3 Ghz laptop chip i'm using now.

Edited by Norman Barrows

Share this post


Link to post
Share on other sites

 

I cannot do the peer to peer topology as I'm using Websockets (Browser based). But I wish I could.


You can have a logical peer to peer topology (one player "hosts" the game instance) while you still use a physical start topology (a single server repeats messages to other players in the same session.)

how do I go about having the monster inch its way closer and closer to the player?


Then you need to have monsters ative when they're close enough that they should know where the player is to start moving towards it.

not sure how to make the server authoritative to track monster movements and AI


Just make it authoritative. If it runs too slow, first look for options to optimize the implemented code, and only when you can't do that anymore, split your world across multiple processes (cores.) I think you over-estimate the "cost" of running simulations on server side. As long as you don't add too much unnecessary indirection or repeated re-processing, you can push a lot of load even on a medium-capable modern CPU.

 

 

Sorry for the late response.

 

I will look into that physical start topology, I will have to incorporate WebRTC somehow as well I'm assuming? 

 

This is what my server-side monster AI looks like right now:

 

5addb35da90941a9fa438fdbe4a88e5b.gif

 

 

If a player uses a skill,  I notify everyone in the game, then check for cooldowns and validate input server-side. Then when that skill collides with a monster, it sends an attack signal to the server (AM 72) -- which then checks if the player is in a certain radius of the monster, etc. Then, it calculates the players damage, damage to mob, etc, then pops out damage numbers.

 

I just don't know if this type of design architecture is the right way to do this? Cooldowns are authoritative and fireball has a 1 second cooldown, and the server checks if a player is next to a mob before doing damage (in a certain radius) -- so they could just send the attack commands in the console to do damage, but they would have to be in that monsters vicinity. And traveling takes a while especially in larger maps. 

Edited by WombatTurkey

Share this post


Link to post
Share on other sites

I will have to incorporate WebRTC somehow as well I'm assuming?


If you want to use UDP, yes. If you're OK with TCP, then websockets alone is good enough.
Some successful web games only use websockets.

I just don't know if this type of design architecture is the right way to do this?


There is no "right way," only "different ways with different trade-offs."

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this