• Content count

  • Joined

  • Last visited

Community Reputation

165 Neutral

About ccherng

  • Rank
  1. I've been trying to figure out how to implement something like the pathfinding in Starcraft 2. I'm not looking for all the sophisticated features like flocking, queueing, etc. In fact I like how in Starcraft 1 the units would interfere with each other. But I do want a path finder better than that used in Starcraft 1.   From the Google searches I've done the various answers have something to do with A* over a navigation mesh and/or dealing with some kind of "visibility graph". But I've gotten somewhat conflicting or unclear answers on what I should do.   One thing I keep encountering has something to do with doing A* over a navmesh. And then use funnel to straighten out the path.   An older post has an answer that says "Starcraft II uses a constrained Delaunay triangulation of the map terrain and buildings to produce a navmesh; A* with a funnel filter is used to path along this mesh, taking into account unit radii; then local steering and collision avoidance layers are added on top of that"   What exactly are the nodes of A* on navmesh? I don't see how any choice of nodes would allow A* on navmesh with a funnel filter to guarantee the path is optimal. But Starcraft II seems to not have the problem of A* going the "wrong way" around an obstacle because of a "shorter" pre-funnel filtered path.   How does Starcraft 2 pathfinding deal with the fact that the units are discs with a finite radius and not points when dealing with corners? And how does it deal with dynamic obstacles like idle units? Units are discs not polygons so treating them as part of the navmesh shouldn't make sense right? And how does pathfinding figure out that big units won't be able to fit through a far away narrow space. For a new buildings added does Starcraft 2 rebuild a new navmesh?   I'm looking for some gritty detailed explaination and not the generic super high level overviews that I've seen typical in search results. It sort of boggles my mind that there isn't a single source detailed explaination tutorial on the basics of the stuff. There is so much stuff out there I don't know what to look at and what to ignore.   If it matters I've already looked at Amit’s Notes about Path-Finding. I've heard of but not read Computational Geometry: Algorithms and Applications. And a blog post about a AI navigation presentation at GDC 2011 mentioned that Starcraft 2 uses a constrained delaunay triangulation for a navmesh. Although the blog post mentions Boids steering and "horizon analysis".   I really wish that guy ApochiPiQ who I quoted above knows the detailed answers to everything and obsessively answers this question.
  2. [color=#333333]In a multithreaded setup with a game logic thread and a render thread, with some kind of skin mesh animation with inverse kinematics plus etc how does animation work? Does the game logic thread just update a number saying time T in the animation and then the render thread infers Who owns the skin mesh animation, the game logic thread or the render thread? How is it stored in the scene graph if it is stored there at all? When the game logic updates does it do the computation of the skin mesh animation and the computation of the inverse kinematics and then store the result directly in the scene graph or is it stored indirectly and the render thread does the computation[/color][left]. [/left][color=#333333]And how does synchronization between game logic and rendering work to prevent writing and reading game state at the same time?[/color] I know that similar type questions have been asked but I've never been satisfied with the answers. I would be very interested in seeing how the game architecture components of a multithreaded triple buffered animation with inverse kinematics all fits together to ensure no race conditions.
  3. [quote name='hplus0603' timestamp='1337661009' post='4942085'] [quote]Why do all fps games have the server send gamestate instead of input which is smaller?[/quote] It is not true that all FPS games do that. Some FPS-es do, because the state is small enough and the player counts are small enough that it doesn't matter (or the recovery from a dropped packet is more important than the bandwidth savings.) Other FPS-es send inputs, and only send state when joining, or when detecting a state mis-match (through CRC, say,) or every once-in-a-while. [/quote] [color=#444444]all the well known fps games send game state: quakes, half lifes, call of duties, etc.[/color] [color=#444444]So I am deeply wondering why the main stream fps games don't consider the solution I proposed[/color]
  4. [color=#333333] Why do all fps games have the server send gamestate instead of input which is smaller?[/color][color=#333333] One reason I can sort of see is that if the server sends input to the clients and a packet gets dropped then the client will not be able to gave an accurate simulation until a resend of that packet occurs which could be an entire timeout plus one way trip latency. Presumably this is considered unreasonable for a real time fps game.[/color][color=#333333] But what if at time T the server sends the input processed at time T to the client and at time T+1 the server sends the input processed at time T and time T+1. This way if the packet containing the input processed at time T is dropped the client will get the next packet sent by the server which contains the input processed at time T and time T+1. Thus the client will not stall on the simulation because the server is redundantly sending previous input. The server stops sending a previous input when it gets an ack from the client.[/color][color=#333333] This seems to avoid sending the entire game state. Can someone tell me why this idea is just bad and why no fps games use it?[/color]
  5. Client-server lockstep for rts

    [quote name='hplus0603' timestamp='1337488345' post='4941577'] Actually, laggers do affect latency, in the sense that the game will run at the speed of the slowest player's physics rate. As long as the lagger can queue commands far enough ahead of time, then the transmission time to the server ("lag" in one sense) does not affect anyone else's game experience. [/quote] Can you explain in detail what you mean? Your comment appears to contradict the quote. So now I am very confused.
  6. In typical fps games how do they determine how far back to rewind when the server sends the authoritative game state. Consider the following example where one way try takes 100 ms. At time T the client sends jump to the server. This arrives at time T+100. The server sends back gamestate with the jump processed and this arrives at the client at time T+200. It would seem the simplest thing for the client to do at time T+200 after receiving the gamestate is to effectively take this gamestate as what should have been the gamestate at time T for client. Thus the client should take this gamestate and simulate from T to T+200 with its buffered input of T to T+200 and use this for the predicted state. However, this in effect would seem to give a prediction of what the server's gamestate will be at time T+300 rather than a prediction of the present state of the server (that is at time T+200). This would suggest that the client should use whatever gamestate it had received at around T+100 and then run simulation from T+100 to T+200 with its buffered input of T+100 to T+200. But knowing to rewind to T+100 is effectively trying to guess what is half the round trip time. Does any of this makes sense and what do typical fps games actually do?
  7. In the article [url=""]http://gafferongames...ame-networking/[/url] there was the following comment which i could not understand: [color=#111111][font=Verdana, sans-serif]"btw afaik StarCraft don’t use peer-to-peer it uses client-server model with lockstep (at least warcraft 3 does so). It has the advantage what theoreticaly laggers will not affect gameplay/response latency at all (but to not let them fall behind server do timeouts so the lagger can catch up, also doing temporary local game speed increasing) and imo it’s the only and true way to do sync in RTS like games. (and for some reasons this technic isn’t good covered in the web) [/font][/color][color=#111111][font=Verdana, sans-serif]most articles are about FPS or peer-to-peer syncs"[/font][/color] Does anyone understand what is meant by client-server model with lockstep and how that allows laggers to not affect response latency? It would seem to me that the lagger would effect response latency as isn't the effect of lockstep is to enforce that all clients synchronously change state so that client input such as lassoing a rectangular area with the mouse always always makes sense.
  8. What advice can you people give me for simple collision detection in 2d? For example, say I use bisection to find a time that was very close to the collision. So now I have two polygons that are almost touching. How can I generate the contact set from this? I am looking for the simplest thing possible. Speed is not an issue. CLARIFICATION: So I think I should clarify what the context of this is. I envision a platform game where there will not be massive amounts of dynamic objects. Nothing like massive stacks. No extremely fast objects. etc. In oth words I am looking for a simple solution to my specific desires. I want ABSOLUTELY NO overlap. I want to use LCP. I don't see how any of the responses so far achieve that [Edited by - ccherng on August 29, 2006 12:16:35 PM]
  9. abc

  10. abc