Jump to content

  • Log In with Google      Sign In   
  • Create Account

Where do I do pathfinding?


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
15 replies to this topic

#1 Triad_prague   Members   -  Reputation: 140

Like
0Likes
Like

Posted 14 October 2011 - 02:25 PM

I'm trying to build a simple test program that is basically a online games where players could walk and chat. the chatting part is not that hard, but the movement is quite stressing. basically, I'm confused at:
-where do I calculate/do the pathfinding? should the server do it and send the calculated waypoint to the client? or should the server only "validates" the path and let the client do the pathfinding?
-a follow up question from question #1:
a. assume I chose the server to do it, wouldn't it be bandwidth intensive to send the calculated path to the client and other players nearby?
b. assume I chose the server to only "validates", will there be a "difference" between the calculated path on the server and the client?
the hardest part is the beginning...

Sponsor:

#2 dpadam450   Members   -  Reputation: 949

Like
0Likes
Like

Posted 17 October 2011 - 02:47 PM

Send the start and end, have the clients compute it.

#3 Triad_prague   Members   -  Reputation: 140

Like
0Likes
Like

Posted 18 October 2011 - 01:54 AM

Send the start and end, have the clients compute it.


so the client sends the start and end point, server validates and simulate it on the server, then tell the client to calculate it?
the hardest part is the beginning...

#4 L. Spiro   Crossbones+   -  Reputation: 14423

Like
3Likes
Like

Posted 18 October 2011 - 03:27 AM

What are you making? Why does the server need to do anything related to paths?
Isn’t it the client who decides the start and end points of a path? Why do you want the server to tell the clients what the start and end points are?

Client decides start and end points.
Client makes path.
Client walks along path.

That is all.
The server keeps the client out of walls, but that has nothing to do with paths. Keeping the client out of walls is something that is done all the time regardless of the client’s “following path” status.


L. Spiro
It is amazing how often people try to be unique, and yet they are always trying to make others be like them. - L. Spiro 2011
I spent most of my life learning the courage it takes to go out and get what I want. Now that I have it, I am not sure exactly what it is that I want. - L. Spiro 2013
I went to my local Subway once to find some guy yelling at the staff. When someone finally came to take my order and asked, “May I help you?”, I replied, “Yeah, I’ll have one asshole to go.”
L. Spiro Engine: http://lspiroengine.com
L. Spiro Engine Forums: http://lspiroengine.com/forums

#5 Triad_prague   Members   -  Reputation: 140

Like
0Likes
Like

Posted 21 October 2011 - 04:28 AM

What are you making? Why does the server need to do anything related to paths?
Isn’t it the client who decides the start and end points of a path? Why do you want the server to tell the clients what the start and end points are?

Client decides start and end points.
Client makes path.
Client walks along path.

That is all.
The server keeps the client out of walls, but that has nothing to do with paths. Keeping the client out of walls is something that is done all the time regardless of the client’s “following path” status.


L. Spiro


well I said the client decides the start and end path, the server only "validates" (check if it's a valid movement) and the client simulate it. what worried me is how would I synchronize the position in the server. so I thought the server needs to simulate the movement too. that would be client and server simulate movement each in their own, but I'm not too sure if that's how it works in most online games :huh:
the hardest part is the beginning...

#6 rpiller   Members   -  Reputation: 706

Like
1Likes
Like

Posted 21 October 2011 - 12:14 PM

This would depend on your game. If it's a board game like chess you want the server validate or else the client could hack it to bypass the client side rule checks. Let's say they make their king move 6 spaces in a zigzag pattern because they were able to bypass the client side rules check. Locally they can do that all they want, but the server would validate that move and realize it's not valid and not update the server board or the opponents client board. So that cheating client is only cheating themselves because now they are out of sync with the server and other client.

Ideally the server would send back to the cheating client a 'no no' msg and move the piece back but chances are if they hacked their client they'll intercept that 'no no' msg and not let it get to the application.

You will want the server to do some kind of validation. It could just be sanity checks like making sure the King in chess only moves 1 tile.

#7 smr   GDNet+   -  Reputation: 1682

Like
2Likes
Like

Posted 21 October 2011 - 01:23 PM

This would depend on your game. If it's a board game like chess you want the server validate or else the client could hack it to bypass the client side rule checks. Let's say they make their king move 6 spaces in a zigzag pattern because they were able to bypass the client side rules check. Locally they can do that all they want, but the server would validate that move and realize it's not valid and not update the server board or the opponents client board. So that cheating client is only cheating themselves because now they are out of sync with the server and other client.

Ideally the server would send back to the cheating client a 'no no' msg and move the piece back but chances are if they hacked their client they'll intercept that 'no no' msg and not let it get to the application.

You will want the server to do some kind of validation. It could just be sanity checks like making sure the King in chess only moves 1 tile.


Do you have to worry about cheating in your chat application? If not, then I wouldn't fret about it too much. Have the pathing be done on the client side. When the client updates the server, the server will check to see if the client is in a valid location. If he is not in a valid location, send back a response that tells them where they should be. The simplest way for the server to do this would be to just send back the player's last known valid position. When the client receives this information it should either: Calculate a new path from the position the server responded with, or simply stop moving altogether. This will get the job done.

It could allow the player to cheat, though. Consider a situation like this:

W: Wall
".": Valid position
@: Player
X: Destination

WWWWWWWWWWW
W....W.....W
W....W.....W
W..@.W..X..W
W....W.....W
W....W.....W
WWWWWWWWWWWW

There is no valid path for the player to the destination X. They're each blocked by walls on both sides. With only validating positions and not paths, the player could send the server a packet with its position inside that unreachable room, and the server would allow it. You can somewhat mitigate this by setting a maximum distance the player can travel between server updates, but that won't work all the time and can cause the client to seem laggy if it can't get updates to the server that often. Another potential solution is to, on the server, draw a line from the player's last known position and the new position and ensure that all positions along the line are valid positions. You could also prevent another kind of cheating using this method by making sure that this line is no longer than the distance the player could actually move in the time between now and when the player was at the last known position.

#8 rpiller   Members   -  Reputation: 706

Like
1Likes
Like

Posted 21 October 2011 - 01:52 PM

I'm confused because it sounds like we are saying the same thing. Have the server do validations/sanity checks.

#9 smr   GDNet+   -  Reputation: 1682

Like
1Likes
Like

Posted 21 October 2011 - 02:07 PM

I'm confused because it sounds like we are saying the same thing. Have the server do validations/sanity checks.


We are. That's the only sane way to do it. I guess we're all just giving ways he could do it on the server

#10 dpadam450   Members   -  Reputation: 949

Like
1Likes
Like

Posted 22 October 2011 - 09:15 PM

What are you making? Why does the server need to do anything related to paths?

Uh well the server needs to tell the other people where this player wants to walk. Send the start and end points to all the players. You could still have some lag though that someone doesnt get the walk command right away and then you will still have some lag issues.

#11 Triad_prague   Members   -  Reputation: 140

Like
0Likes
Like

Posted 23 October 2011 - 03:44 AM

dpadam is right. that's the issue I'm facing now. Basically what confuses me is when the server should tell other players about playerA location. That means the server MUST have the up-to-date playerA location. Which means it HAS to simulate path movement too. And it will synchronize the valid path perhaps once every 2 seconds. What do you guys think about it?

1. playerA tell the server it wants to move from 10,23 to 42, 21
2. the server checks the path
3. if it's invalid, send nothing to playerA
4. otherwise, tell playerA to simulate movement from 10,23 to 42, 21. the server simulates the movement too
5. if there's another player nearby, tell the player that playerA is moving from [current pos] to 42,21
6. once every 2 seconds server tell ALL players their true location in the server

that's just my design, and it hasn't been proven yet :P
the hardest part is the beginning...

#12 DarklyDreaming   Members   -  Reputation: 366

Like
1Likes
Like

Posted 23 October 2011 - 04:49 AM

What are you making? Why does the server need to do anything related to paths?

Uh well the server needs to tell the other people where this player wants to walk.
[-snip-]

Wait, what?

Do all the "other people" really need to know where the player wants to walk?
So, you're telling me that playerB needs to know where playerA wants to move? As in, he needs the actual path that playerA is moving along? I don't buy that...

Why not just let the client update playerA's movement -> server side correction -> propagation to other players. Done? Where in this does there ever come a need for all the players to know the path that playerA has chosen? (I'm genuinely wondering)
"I will personally burn everything I've made to the fucking ground if I think I can catch them in the flames."
~ Gabe

"I don't mean to rush you but you are keeping two civilizations waiting!"
~ Cavil, BSG.
"If it's really important to you that other people follow your True Brace Style, it just indicates you're inexperienced. Go find something productive to do."
~ Bregma

"Well, you're not alone.

There's a club for people like that. It's called Everybody and we meet at the bar."

~ Antheus


#13 wodinoneeye   Members   -  Reputation: 879

Like
1Likes
Like

Posted 23 October 2011 - 06:01 AM

Client calculates path, from player indicating new endpoint and start point assumed to be current position (it might be rendering some catchup due to latency but will be at the 'official' current point eventually before starting next increment.

Server will validate each step of the path as it is fed each step one by one by the client. These steps have small enough increments in the coordinate changes so that the validation wont skip terrain features (triangles on a navmap or cells on a regular grid, or a squeeze check of a bounding box against the terrain mesh,etc).

Thus the server doesnt have to do heavyweight recreation of the pathfinding (and wont waste the effort when the player keeps changing direction and most of the path processing is invalidated and useless)

The server validation still may do a fair bit of processing (ie- the bounding box collision for a small movement step) but not for the entire path.

The client itself probably will only do a test a short distance along in the future moves (depending on how far out front the player can indicate the endpoint via input) and stop if the collision validation fails.

Some games simply stop the motion, others have the object bounce off or slide the edge (or even spin on impacts)

With games that have collision detection with dynamic object/terrain then the path can go invalid immedaitely as soon as something moves to block the expected path.
The data potentialy arriving late for dynamic movements (latency) in the environment may have to be handled specially (cleverly) to handle these immediate collisions
--------------------------------------------Ratings are Opinion, not Fact

#14 Triad_prague   Members   -  Reputation: 140

Like
0Likes
Like

Posted 23 October 2011 - 06:35 AM

Of course the server won't send "playerA move" message to all other players, only those in playerA's vicinity...

@woodinooneeye, hey your idea's kinda good. Tell me if I'm wrong interpreting your ideas:


1. playerA request movement from 20, 21 to 40, 51
2. server checks if it's valid path
3. if it's invalid, send nothing
4. otherwise, tell playerA to simulate the path movement

5. while simulating(movement), the client send new coordinates each x MS (x is tweakable)
6. server get the new coordinates each x MS, and broadcast it to other players within playerA's vicinity

am I right? the thing is, the client could potentially cheat by sending new coordinates even if the path is invalid (the cheater could just ignore the "invalid_path" message)

EDIT: I just noticed that all of you're suggesting the same ideas, well I'm sorry for being so dumb. But still, please answer my question (about how to avoid cheaters) above...hehe :D
the hardest part is the beginning...

#15 dpadam450   Members   -  Reputation: 949

Like
1Likes
Like

Posted 23 October 2011 - 12:43 PM

What you are doing is basically networking a real time strategy architecture with a fps style game. If there are only so many players and you control one of them, you can get away with just sending updates of the players position as what is suggested.

So you can either validate, and then continue sending movement updates every 15ms. Or you can validate movement while you receive them instead of up front. If you get a movement command, check the current tile the player is now on, if it is invalid then send a stop command and move them back or something.

#16 Triad_prague   Members   -  Reputation: 140

Like
0Likes
Like

Posted 23 October 2011 - 12:52 PM

wow it works!! well I need a bit of optimizations still, but thanks for sharing your ideas guys!! :D
the hardest part is the beginning...




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS