Client/Server Game + MovementValidation

[Grofit]

Hey,

Im just trying to think if there is a *better* way of solving the scenerio im about to reel off, currently i cant think of one but it feels like it will just eat into CPU time...

First of all the client runs a 2d based game that is for all intents and purposes tileset based, although collisions are not done *per tile* its pretty similar, and its easy enough to just say that each tile which is 32x32 is split into 4 16x16 collision sections.

Now the game world is split up into > 100 areas, each area being a 2d zone of anywhere between 10x10 and 10000x10000 tiles, although its usually in the realm of a 1000 or so.

The server will have > 100 players connected at any one time and although it limits player chatter to surrounding areas in this scenario lets just pretend its done on a zone by zone basis. So if someone moves in Zone 1 only people in Zone 1 will need that update.

Now the main problem i have is that when the player clicks to move to position 800,200 and is currently at 100,100 i need to have the server validate if this movement is allowed before letting them carry it out. As there is no real way to know that a movement is valid unless there can be a path found between the current position and the end position it seems that i would need to do a path finding check for each movement. This makes me feel a bit iffy and this is where im not sure if there is a better way, but i cant see an obvious one...

The server will have the zones loaded in memory, although it only has a collision map style structure, as thats all it cares about, and will basically locate the players current waypoint and the players end point, if it finds a path it sends back a valid response to the client, then the client will run its own pathfinding to find its way to the position, as will all other clients who are listening to updates from the moving player...


Now in the above scenario i cant trust the client to validate the movement, so it seems like it HAS to fall to the server to do this, but as its going to be doing alot of other stuff too it seems like it could just keel over and die... ive got a basic A* algorithm implemented but it is not that efficient and is using Lists at the moment (as i just wanted to knock something quick and dirty together to check how fast/slow it was), and its pretty slow (realm of like 30ms for a simple path find) and im sure it can be speeded up a HUGE amount if i was to make everything structs and use some sort of priority queue... but i thought that i would just check here and see if anyone knows of a better way to do this sort of thing...

Also if this is the best/only way to do it, im not after the shortest path to the given target im just wanting to know if it is possible to reach the given point, so is there any better suited algorithm for doing this, so the clients could still use A* (although a much improved implementation of it), and the server could use some other algorithm to speed up the validation...

Sorry for all the waffling like normal, just want to give you a fuller scenario to work with :D

[sotoasty]

How about have the client create the path, then have the server validate it. That should at least cut down on the possibilities that the server would have to go through to return a response.

[MadHatter]

pathfinding can be a fairly simple process (one i'd think the server would even be better equipped to do than a client, at least of larger 3d games), especially if you are using proper segmentation techniques.

if you are even asking this question, you should take the safest approach and do it all on the server. client passes input (the click point where they want to go) to the server who processes it, and passes back to the client in the client's update, where to move the piece. the server can take the two points, do a path finding pass to determine whether the player can move there, then send an update of move from here to there at which point the client does the path finding for animation purposes only (or could receive a set of points to travel on, though I'd probably opt for the former).

I'm pretty sure this question has been discussed to death somewhere like gamedev.net. try searching there for solutions.

[Grofit]

Hey,

Yeah i was going to post there, but im currently at work and its blocked :(

Thats the way im currently doing it, pass over 2 points and the server will either allow the update or fail it. Then the clients will all be told of the user updating their position and will all do client side path finding to reach the destination...

I wouldnt send the client paths around as i would be sending over way too much data every time the player clicks, CPU time is cheaper than bandwidth...

Most of the areas are split up in quadtrees, however when an area/level is loaded it is analyzed by the pathfinder and waypoints are generated for the possible static collision points, then each waypoint is hooked up to its neighbours, so it never acctually needs to look up anywhere outside of its current node as it can tell it exactly what it links to and the cost of the move without having to do lots of lookups, it takes up slightly more memory but speeds up the lookups... although it seems most C# based path finding implementations are slower than slow, so i will need to look into improving it...

The original reason i was asking this question was to see if there was a better way to find if there is a valid route between 2 points, rather than finding the quickest path, that way i can speed up the server lookups and just let the client worry about finding the quickest path...

[MadHatter]

maybe I'm not following the collision points but shouldn't you be able to cache paths to some degree (store each a->b point as a rectangle of some size then determine whether new points are inside the rect[a] or rec[b] areas) and cut down your processing quite a bit?

[Grofit]

maybe I'm not following the collision points but shouldn't you be able to cache paths to some degree (store each a->b point as a rectangle of some size then determine whether new points are inside the rect[a] or rec[b] areas) and cut down your processing quite a bit?

Sorry i think maybe im being a dunce here, what exactly do you mean? make spatial partitions of the collision data?

Currently i generate waypoints on a given step size, so lets say 16x16, which then scans the level and all its collisions and then create a quadtree of the waypoints (x,y and any static cost assigned). Then it does a 2nd pass and hooks up any neighbours. This can then be passed into a similar method if required to create a 2nd layer at a larger step size and then again they are hooked up, so you can have a 2 tier waypoint system, you could even make more layers if you want, so each layer is in its own Quadtree. This is done once, when the level is loaded and then stored for the path finding checks.

Then the A* neighbour lookups are pretty much done for free, and only possible paths are available.

Now is the idea you are mentioning caching valid paths (so solution paths) and then somehow re-using them if someone wants to travel to a similar position? im not sure how i could implement that or how it would speed it up if i was having to do another set of lookups on cached paths... but maybe its just because i havent seen a decent article on it yet...