Jump to content
  • Advertisement

jacksaccountongamedev

Member
  • Content Count

    818
  • Joined

  • Last visited

Community Reputation

546 Good

About jacksaccountongamedev

  • Rank
    Advanced Member

Personal Information

  • Interests
    Design
    Programming

Recent Profile Visitors

The recent visitors block is disabled and is not being shown to other users.

  1. jacksaccountongamedev

    Close Quarters Development: Realistic Combat AI Part I

    That's correct. When the AI opts to attack, it generates a path from its current position (usually behind cover) to an attack position, i.e. one that overlooks the target's last known position while also being outside of the target's firing cone. If the bot reaches its attack position and finds that the target isn't visible, it guesses the target's new position by taking the target's last known position and looking for cover from itself in its current (attack) position. The bot then generates a new attack path to the guessed position. The bot repeats this process until it spots the target, acquires a new one, or the memory "fact" pertaining to the target expires (10 seconds). The effect is that if a bot loses track of its enemy, it goes searching for it. The main drawback is that because bots don't keep track of where they've already looked, sometimes two bots searching for each other will circle around an obstacle in the same direction. This issue will be automatically resolved once I allow the bots to hear footsteps (currently they only hear gunfire).
  2. Although Close Quarters is primarily a multiplayer game, it must feature challenging AI bots so that players can still have fun when their internet connection is poor or there are no other players online. Bots will also play an important subsidiary role in some game modes. Hence, the bots must behave believably and manifest a range of complex behaviours, such as using cover, using items at opportune times, flanking, and throwing and escaping grenades. The environment and the constraints: The game environments consist of polygons. Most polygons block movement, sight, and gunfire, though there are some “low” polygons that only block movement. The environments are densely packed with obstacles and cover options. The AI is also constrained by several technical factors. Most importantly, the server–which runs bots when few players are online–must perform well on an inexpensive VPS with at least ten bots. Moreover, CPU usage should be low enough to run multiple server instances on the one VPS without maximizing the CPU allotment and thereby irritating the VPS provider. Figure 1: Environments Figure 2: A player’s view with obstacles blocking sight (grey areas are obscured) Navigation and visibility mesh and tactical pathfinding: The bots rely on a dense navigation mesh consisting of discrete points. The mesh is generated by first expanding and combining the polygons constituting the environment. Extra nodes are added near corners as these locations are the most likely to offer sensible cover positions. The resulting walkable space is then triangulated to generate the mesh. Figure 3: The navigation mesh As the bots need to perform tactical pathfinding, the navigation mesh must hold visibility data that allows us to quickly test whether a node has cover from given enemy. Each node therefore contains an array of 24 bytes, each representing the precomputed approximate distance between the node and the nearest sight-blocking obstacle in a certain direction. Figure 4: Visibility data (blue lines) stored in a node. Each line represents a one-byte value indicating visibility in a given direction. With this data, it is possible to perform A* graph searches on the navigation mesh wherein nodes that are probably exposed to known enemies are penalized without performing many costly line-of-sight checks. To test if a given node is exposed to an enemy, we determine the direction and distance from the node to that enemy and then check whether that distance is lower than that stored in the array element corresponding most closely to that direction. Additionally, we may check whether the enemy is facing the node. When we apply a penalty multiplier to the traversal cost of exposed nodes, the resulting path tends to avoid such nodes. The same visibility data can be used for other “tactical” actions besides pathfinding between two predetermined points. For example, a bot seeks cover by executing a breadth-first search and stopping once it finds a covered node. Actual line-of-sight checks are used to verify that a node that seems to provide cover actually does. Similarly, we can generate flanking attack paths by executing an A* search towards the target while heavily penalizing exposed nodes within its firing cone and stopping once we reach an exposed node outside of that firing cone (One problem with this approach is that bots left out of sight tend to constantly advance towards their target and therefore seem too aggressive, though it could perhaps be solved by adjusting the A* heuristic to guide the bot not directly towards the target but towards any nodes a preferred distance away from the target). Bot senses and memory: For the bots to behave believably, they must not be seen as “cheating”. In other words, the information a bot works with should be similar to the information a player would have in its place. For example, an enemy behind an obstacle should be hidden from the bot just as it would be hidden to a player. There are two ways a player might discover an enemy’s position: they may see the enemy, or they may hear the enemy moving, shooting, or performing some other action. Each bot maintains a list of known “facts” about enemies’ positions and orientations. These facts expire after ten seconds pass without updates. A fact pertaining to a given enemy is updated whenever the bot can see or hear that enemy. To simulate uncertainty, when a bot hears an enemy, the resulting position of the relevant fact is offset from the enemy’s actual position in a random direction and distance based on how close the sound was to the bot (see video at 1:28). Figure 5: Facts (pink circles) in a bot’s memory Behaviour tree: In an earlier version of Close Quarters, the AI used STRIPS, an approach popularized by F.E.A.R. in 2005. In STRIPS, the relationships between different AI behaviours are not predetermined by the programmer. Rather, each behaviour contains a list of binary preconditions and outcomes. Each bot has a goal world state and then uses an A* graph search to find a sequence of behaviours that would achieve it. This approach worked well, but I felt that it was overkill for this application and better suited to AI that needs to develop elaborate plans involving many different behaviours. In most cases, I already knew the circumstances under which I wanted a bot to execute one behaviour or another, so using A* to determine that was an unnecessary waste of CPU resources. Hence, this time around the bots use a simple decision and behaviour tree. Each step, a bot traverses the tree from the root until it reaches a behaviour. If that behaviour is the one already being executed, the bot continues that behaviour. If not, the bot initiates the behaviour and begins running it. Some behaviours can “block”, meaning that they will prevent the bot from re-traversing the tree until some condition is met. This is useful, for example, when ensuring that bots properly make it behind cover before deciding to attack. Behaviours can also “cancel” themselves, forcing a re-traversal of the tree and re-initiation of the behaviour. This is useful, for example, when a bot is fleeing a grenade and another grenade appears compromising the chosen flight positions. Figure 6: The current decision and behaviour tree Some secondary behaviours are coded within other, more general behaviours. For example, if a bot tries to attack an enemy and finds that the enemy is not in its suspected position, the bot estimates where the enemy might now be and calculates a new attack path without ever exiting the attack behaviour. Distributing the load: It is not necessary that every bot be updated every physics frame, i.e. 40 times per second. To reduce CPU usage, each bot only “thinks” 20 times per second (a figure that could be further reduced if necessary). Hence, on each physics step, the AI of only half the bots is updated. Grenade handling: One major challenge is having the bots use grenades intelligently. Grenade handling is much more complicated than shooting because grenades can be bounced off walls, have an area effect, and take time to throw. Luckily, the bots don’t need to use grenades perfectly, just sensibly. Traditional approaches to this problem include precomputing grenade trajectories at navigation nodes, but doing so added several seconds to each map’s load time, which conflicts with my goal of having Close Quarters place players in a battle within a few seconds of opening the game. Hence, the bots look for opportunities to use grenades by calculating grenade trajectories on the fly. Each step, an attacking bot will test several viable trajectories in a given direction up to 60 degrees away from the direction to the intended target. If a grenade thrown along a trajectory tested might kill the target and the target is out of sight, the bot throws a grenade. The test direction is cycled each AI step. Figure 7: The directions a bot will test over the course of one second (pale pink lines) and the trajectories tested (blue circles) along the direction selected in the current step (solid pink line). The bots’ grenade use is therefore opportunistic as a bot will not move to a position specifically to throw a grenade. However, the path that a bot chooses to attack an enemy will often also be a sensible path from which to throw a grenade. A significant drawback is that the limited number of directions tested means that bots will miss opportunities to bounce grenades off small obstacles. This is most noticeable around doorframes, where bots usually won’t recognize an opportunity to use a grenade. This issue could be addressed by testing multiple directions each frame and thereby reducing the angle between a test direction and the one that follows. Towards more human behaviour: One issue that quickly became evident was that bots were too quick on the trigger, so they were very difficult to beat in a one-on-one engagement. The average human reaction time to visual stimuli is 250 milliseconds, but at 20 steps per seconds, the maximum bot reaction time would only be 50 milliseconds! To address this issue, I added an intentional delay between when a bot acquires a shot and when it shoots, bringing its reaction time insofar as shooting is concerned more in line with a human player’s reaction time. Further development: The above systems provide a strong foundational AI, but there is room for major improvements. For example, currently, a bot’s spatial reasoning is limited to its immediate environment, so while a bot usually tries to flank its enemy, it will often miss flanking paths around rather large obstacles. Similarly, bots are only roughly aware of their teammates’ presence, so they will sometimes clump up when it makes more sense to split up and flank. Hence, the future devlogs in this series will cover: Squad-level AI, including coordinated flanking and suppressing fire, and higher-level spatial reasoning Deliberately assisting human teammates Following a human player’s orders You can play the in-development version of Close Quarters here and follow its development on Reddit or Twitter. This post was discussed here. Note: This post was originally published in the Close Quarters Devlog, and is reproduced here with the kind permission of the original author.
  3. Close Quarters Development: Realistic Combat AI Part I Although Close Quarters is primarily a multiplayer game, it must feature challenging AI bots so that players can still have fun when their internet connection is poor or there are no other players online. Bots will also play an important subsidiary role in some game modes. Hence, the bots must behave believably and manifest a range of complex behaviours, such as using cover, using items at opportune times, flanking, and throwing and escaping grenades. The environment and the constraints: The game environments consist of polygons. Most polygons block movement, sight, and gunfire, though there are some “low” polygons that only block movement. The environments are densely packed with obstacles and cover options. The AI is also constrained by several technical factors. Most importantly, the server–which runs bots when few players are online–must perform well on an inexpensive VPS with at least ten bots. Moreover, CPU usage should be low enough to run multiple server instances on the one VPS without maximizing the CPU allotment and thereby irritating the VPS provider. Figure 1: Environments Figure 2: A player’s view with obstacles blocking sight (grey areas are obscured) Navigation and visibility mesh and tactical pathfinding: The bots rely on a dense navigation mesh consisting of discrete points. The mesh is generated by first expanding and combining the polygons constituting the environment. Extra nodes are added near corners as these locations are the most likely to offer sensible cover positions. The resulting walkable space is then triangulated to generate the mesh. Figure 3: The navigation mesh As the bots need to perform tactical pathfinding, the navigation mesh must hold visibility data that allows us to quickly test whether a node has cover from given enemy. Each node therefore contains an array of 24 bytes, each representing the precomputed approximate distance between the node and the nearest sight-blocking obstacle in a certain direction. Figure 4: Visibility data (blue lines) stored in a node. Each line represents a one-byte value indicating visibility in a given direction. With this data, it is possible to perform A* graph searches on the navigation mesh wherein nodes that are probably exposed to known enemies are penalized without performing many costly line-of-sight checks. To test if a given node is exposed to an enemy, we determine the direction and distance from the node to that enemy and then check whether that distance is lower than that stored in the array element corresponding most closely to that direction. Additionally, we may check whether the enemy is facing the node. When we apply a penalty multiplier to the traversal cost of exposed nodes, the resulting path tends to avoid such nodes. The same visibility data can be used for other “tactical” actions besides pathfinding between two predetermined points. For example, a bot seeks cover by executing a breadth-first search and stopping once it finds a covered node. Actual line-of-sight checks are used to verify that a node that seems to provide cover actually does. Similarly, we can generate flanking attack paths by executing an A* search towards the target while heavily penalizing exposed nodes within its firing cone and stopping once we reach an exposed node outside of that firing cone (One problem with this approach is that bots left out of sight tend to constantly advance towards their target and therefore seem too aggressive, though it could perhaps be solved be adjusting the A* heuristic to guide the bot not directly towards the target but towards any nodes a preferred distance away from the target). Bot senses and memory: For the bots to behave believably, they must not be seen as “cheating”. In other words, the information a bot works with should be similar to the information a player would have in its place. For example, an enemy behind an obstacle should be hidden from the bot just as it would be hidden to a player. There are two ways a player might discover an enemy’s position: they may see the enemy, or they may hear the enemy moving, shooting, or performing some other action. Each bot maintains a list of known “facts” about enemies’ positions and orientations. These facts expire after ten seconds pass without updates. A fact pertaining to a given enemy is updated whenever the bot can see or hear that enemy. To simulate uncertainty, when a bot hears an enemy, the resulting position of the relevant fact is offset from the enemy’s actual position in a random direction and distance based on how close the sound was to the bot (see video at 1:28). Figure 5: Facts (pink circles) in a bot’s memory Behaviour tree: In an earlier version of Close Quarters, the AI used STRIPS, an approach popularized by F.E.A.R. in 2005. In STRIPS, the relationships between different AI behaviours are not predetermined by the programmer. Rather, each behaviour contains a list of binary preconditions and outcomes. Each bot has a goal world state and then uses an A* graph search to find a sequence of behaviours that would achieve it. This approach worked well, but I felt that it was overkill for this application and better suited to AI that needs to develop elaborate plans involving many different behaviours. In most cases, I already knew the circumstances under which I wanted a bot to execute one behaviour or another, so using A* to determine that was an unnecessary waste of CPU resources. Hence, this time around the bots use a simple decision and behaviour tree. Each step, a bot traverses the tree from the root until it reaches a behaviour. If that behaviour is the one already being executed, the bot continues that behaviour. If not, the bot initiates the behaviour and begins running it. Some behaviours can “block”, meaning that they will prevent the bot from re-traversing the tree until some condition is met. This is useful, for example, when ensuring that bots properly make it behind cover before deciding to attack. Behaviours can also “cancel” themselves, forcing a re-traversal of the tree and re-initiation of the behaviour. This is useful, for example, when a bot is fleeing a grenade and another grenade appears compromising the chosen flight positions. Figure 6: The current decision and behaviour tree Some secondary behaviours are coded within other, more general behaviours. For example, if a bot tries to attack an enemy and finds that the enemy is not in its suspected position, the bot estimates where the enemy might now be and calculates a new attack path without ever exiting the attack behaviour. Distributing the load: It is not necessary that every bot be updated every physics frame, i.e. 40 times per second. To reduce CPU usage, each bot only “thinks” 20 times per second (a figure that could be further reduced if necessary). Hence, on each physics step, the AI of only half the bots is updated. Grenade handling: One major challenge is having the bots use grenades intelligently. Grenade handling is much more complicated than shooting because grenades can be bounced off walls, have an area effect, and take time to throw. Luckily, the bots don’t need to use grenades perfectly, just sensibly. Traditional approaches to this problem include precomputing grenade trajectories at navigation nodes, but doing so added several seconds to each map’s load time, which conflicts with my goal of having Close Quarters place players in a battle within a few seconds of opening the game. Hence, the bots look for opportunities to use grenades by calculating grenade trajectories on the fly. Each step, an attacking bot will test several viable trajectories in a given direction up to 60 degrees away from the direction to the intended target. If a grenade thrown along a trajectory tested might kill the target and the target is out of sight, the bot throws a grenade. The test direction is cycled each AI step. Figure 7: The directions a bot will test over the course of one second (pale pink lines) and the trajectories tested (blue circles) along the direction selected in the current step (solid pink line). The bots’ grenade use is therefore opportunistic as a bot will not move to a position specifically to throw a grenade. However, the path that a bot chooses to attack an enemy will often also be a sensible path from which to throw a grenade. A significant drawback is that the limited number of directions tested means that bots will miss opportunities to bounce grenades off small obstacles. This is most noticeable around doorframes, where bots usually won’t recognize an opportunity to use a grenade. This issue could be addressed by testing multiple directions each frame and thereby reducing the angle between a test direction and the one that follows. Towards more human behaviour: One issue that quickly became evident was that bots were too quick on the trigger, so they were very difficult to beat in a one-on-one engagement. The average human reaction time to visual stimuli is 250 milliseconds, but at 20 steps per seconds, the maximum bot reaction time would only be 50 milliseconds! To address this issue, I added an intentional delay between when a bot acquires a shot and when it shoots, bringing its reaction time insofar as shooting is concerned more in line with a human player’s reaction time. Further development: The above systems provide a strong foundational AI, but there is room for major improvements. For example, currently, a bot’s spatial reasoning is limited to its immediate environment, so while a bot usually tries to flank its enemy, it will often miss flanking paths around rather large obstacles. Similarly, bots are only roughly aware of their teammates’ presence, so they will sometimes clump up when it makes more sense to split up and flank. Hence, the future devlogs in this series will cover: Squad-level AI, including coordinated flanking and suppressing fire, and higher-level spatial reasoning Deliberately assisting human teammates Following a human player’s orders You can play the in-development version of Close Quarters here and follow its development on Reddit or Twitter. This post was discussed here.
  4. jacksaccountongamedev

    Need help optimizing the bandwidth

    Hi TufanMeric, I’ve been working on a game with some similarity to the one you mentioned. Here’s some things to consider: 1. 60 updates per second seems excessive. Even 30 might be more than necessary if your players don't change velocity quickly. I send 20 per second, i.e. one every two physics frames. Instead of trying to send an update for every rendering or physics frame, send fewer updates and smooth/interpolate/extrapolate the motion client-side. 2. Don’t send clients irrelevant data. The client does not need to know about things that are out of its view. For my game, players only receive updates for other players and events within a distance of 1000 units, i.e. just further than the player can see. Things that are further away but that the player would still hear (e.g. gunshots and explosions) are sent as 3-bytes (1 byte for the id of the sound to play and 2 bytes for an approximation of the location). 3. Each packet you send comes with significant overhead, so try to reduce the overall number of packets. For instance, my client, rather than sending a separate packet to the server every time the player fires a bullet, appends the necessary information about the bullet to the outgoing movement updates. Since the client is sending movement updates 20Hz and the game’s physics run at 40Hz, my players can only fire bullets on even numbered physics frames, but in-game this restriction isn’t very noticeable. 4. Try to pack your data densely. Often, data does not need to be sent in the same format or resolution in which it is stored locally. For example, my client sends position data as well as input data. It sends the player’s last four X/Y positions (two of which will be new for the sever and two for the purpose of redundancy to reduce the effect of lost and out-of-order packets). Locally, these values are stored as floats. That’s eight floats, or 24 bytes. However, as the maximum play area is 7500x7500, I send the player’s current position using 2-byte integers and thereby achieve a resolution of about 0.11 – the inaccuracy is totally invisible. Then, because players can move at most 3.5 units in a single physics frame, the other three positions are sent as 1-byte relative values (which provides a resolution of about 0.01). So instead of sending 24 bytes of positional data, I only send 10. Ditto for input: all the player’s input can be packed into a single byte rather than sending a separate byte for every key. My examples mainly concerned client-to-server communication, but naturally, the same applies to data flowing the other direction. What do your update packets look like?
  5. jacksaccountongamedev

    Can I make Websocket multiplayer games for any genre?

    Are you sure that is the case for WebSockets? I haven't found any sources to confirm it, and it doesn't quite line up with my own experiments/observations.
  6. jacksaccountongamedev

    Can I make Websocket multiplayer games for any genre?

    Another thought to add: There is a fairly serious FPS around at the moment that uses or was using TCP. It's called Ironsight. I haven't followed it, but I saw that people were complaining about the TCP and that the developers made an (unsuccessful?) effort to switch to UDP. It's probably be worth looking into if your interested in exploring the feasibility of TCP in shooter.
  7. jacksaccountongamedev

    Can I make Websocket multiplayer games for any genre?

    It certainly should be smooth because you weren't connected to any server! In other words, there was no networking occurring. Furthermore, client-side prediction means that even when connected, your own movement should seem totally smooth unless there are significant hiccups in the connection prompting the sever to force a re-sync of the player's position. The real test, then, is whether other players' movements seems smooth (especially because although they are interpolated on the server, they are extrapolated on the client). Unfortunately, until I add bots, there will be no way to see that without other players connected. My intent behind including the link was (besides the shameless plug) to show you a kind of movement mechanics that can work OK via less-than-ideal WebSockets (albeit five per player), at least according to my limited, small-scale testing. Inertia and acceleration help mitigate latency; that's how SubSpace was able support servers of 50 players on dial-up connections with RTTs of 200-400ms twenty years ago. But if you want players to instantaneously change their velocity (i.e. your gameplay centers on reflexes), then you probably need optimal networking conditions. I'm breaking a lot of rules (e.g. using TCP and using a virtual private server), so it'll be interesting to see just how well this game does or doesn't function on a larger scale. Certainly, I'm assuming that players will have reasonably stable connections to a sever in their general region (so no mobile players?). I'm not quite sure how much, if at all, round-trip-time will be affected. The development of the UDP client is behind the development of the WebSocket client, so currently it's very hard to test them together. I fully expect UDP players to have less issues with lag between them and the server (because of no head-of-line blocking and because of faster re-transmission of lost packets), but it remains to be seen whether this will translate to any real advantage in-game because they are also, to some extent, at the mercy of the other players' connections. As I mentioned in the other thread, the game does support UDP-only servers because if it became popular, I can envisage a demand for them. Whoever runs a sever can select what types of connections to allow. The obvious advantage will be had by a player hosting a non-dedicated server, who will be the only one seeing the true positions of other players. I'm not too worried about this as it could be an incentive for players to go to the trouble of hosting their own games. Of course, for a true UDP experience in the browser, there's always WebRTC. I experimented with it before beginning with WebSockets, but I thought there were some obstacles that are relatively insurmountable for a lowly hobbyist, namely NAT-traversal and the need to run your own TURN servers, the difficulty of integrating WebRTC with C++, and the general lack of support, documentation, and communal experience. WebRTC seems like completely uncharted territory - I'm not aware of any game currently supporting it, but I'm sure other people know more than I do.
  8. jacksaccountongamedev

    Can I make Websocket multiplayer games for any genre?

    Hi Hashbrown. Regarding FPSs: I’m the one who started the previous thread linked in Hodgman’s post. Since that thread, I’ve quietly done steady work on the game. It's not a FPS, but the mechanics and networking code are similar. We did a small WebSocket multiplayer test last week and it went really well. That was five players in Jordan connecting to a VPS in France. You can get an idea of just how “fast paced” the game is here. The server is off at the moment, but you can still see how responsive the movement is, the use of inertia, projectile speed, etc. - it's less twitched-based than some shooters. As mentioned in the thread, I’m round-robining over five WebSocket connections. It’s working well so far, but I plucked that number right out of a hat - I haven't tested other configurations to make any kind of comparison, and I haven't tested with a large number of players. (If you want to observe the networking in action, PM me and I'll figure out a time to have the server on.) In light of all that, my preliminary observation is that WebSockets could work OK for a FPS. But I think the networking code needs to be extra good (naturally), and there are definitely some allowances I have made because of the less-than-ideal TCP/browser environment. For example, my clients have more authority over their position than is typical in a multiplayer shooter. This mitigates the effect of interruptions in the flow of updates from the client to the server but makes it harder to prevent cheating (a particularly big problem because users can use the browser itself to easily access and change some parts of the game's code). You should also have a look at multiplayer shooters (2D or 3D) among the ".io" games. That should give you a good idea of what's already been done. In my opinion, most have a sluggish feel. Most don't seem to do any kind of client prediction, but I suspect that has more to do with the way these games are programmed than with limitations imposed by the WebSocket platform itself. Regarding RTSs and RPGs, these seem like ideal applications for WebSockets.
  9. jacksaccountongamedev

    Using concurrent TCP/WebSockets to mitigate head-of-line blocking

    Thanks for the comments. I'm slow in responding to this thread because a discussion has been going on between me and another forum user here. The discussion covers a few points, including the code to handle the connections and the possibility of implementing a system of acknowledgements in order to avoid sending packets down potentially blocked connections. I've been testing, on a small scale, the idea of rotating across five sockets and it has been working well so far.
  10. Hello. I’m looking for some advice on how my C++ multiplayer shooter should handle WebSocket connections. The game is fast-paced, but movement is slower than in many first-person shooters (and could potentially be slowed further if necessary). Background/basic design: My game has two versions. The first is a standalone desktop version. The second is a web version compiled via Emscripten/WebAssembly and running in the browser (see above link). The basic idea is to support both casual players wanting (or needing) to run the game in the browser and players wanting to download and run the standalone version. Players using the web/browser version connect to the server via WebSockets (i.e. TCP). Players using the standalone version usually connect via UDP. The same server can handle both kinds of connections. In other words, players playing via the browser/WebSockets can currently play in the same server as those playing via the standalone application/UDP, though a server can be configured to only accept one kind of connection (e.g. UDP-only servers). A server may be dedicated, or it may be hosted by a (port-forwarding) player using the standalone application and participating in the game. Questions re. TCP/WebSockets: Obviously, the UDP players can expect less lag issues than the WebSocket players. To mitigate the problem of head-of-line blocking for the WebSocket players, my plan is that each client connecting from the browser will connect to the server through several concurrent WebSockets. A similar system was used in Airmash, which was a pretty successful action game using WebSockets that didn’t seem to suffer from lag issues. According to its creator, each client in Airmash connected via two WebSockets, with important information being duplicated and sent on both connections. My plan is that rather than sending important information across all open socket connections between the server and a client, the two would simply cycle through the open connections. That way, if a packet is lost, the blocked connection will have some time to recover before it is used again. Also, even if the connection is still blocked by the time it needs to be used again, other data would still be arriving through the other connections. 1. Is this actually a viable way to mitigate head-of-line blocking? Obviously, nothing can be done about a hiccup in the client’s connection to the internet, but would this technique actually help reduce the effect of occasional lost packets? Or would a packet dropped from one connection somehow also block the others such that there's no point in using multiple concurrent connections? 2. If it is viable, then what would be a reasonable number of WebSocket connections to establish between each client and the server? The amount of data that needs to be transmitted would remain mostly the same irrespective of the number of connections, so more connections means less load on each one. If updates are sent at 20hz and there are only two connections between the client and the server (as in Airmash), then one connection would get used every 100ms, which probably isn’t enough time to recover from a dropped packet. On the other hand, if there are ten connections between a client and the sever, then each connection has half a second to recover from a lost packet before its turn to be used again comes around. 3. Finally, are there any glaring issues regarding the design outlined above? The idea of accepting both UDP and TCP connections on one server to accommodate players in different environments seems novel, but could these different kinds of connections somehow interfere with each other? Thanks for any input/advice! To be clear, I have a basic understanding of game networking but am certainly not experienced in this area.
  11. jacksaccountongamedev

    How to deal with hetergeneous agent size in pathfinding

    Hi Jack, Alvaro's solution won't well work for a robust navigation mesh system. Please see my response in this thread. In it, I discuss the problems introduced by accounting for agents of different sizes as well as how to resolve them.
  12. jacksaccountongamedev

    Navmesh without agent radius offsets

    Hi DrEvil, Sorry that it’s taken me a little while to get back to your post/PM. I’m really under the pump with work at the moment. To account for agents with varying sizes, we need to solve two problems: 1. We need to account for agent size when running our A* algorithm on the navigation mesh to find the list of nodes (be they triangles or convex polygons) which will contain the final path. That is to say, we can't send agents through gaps that are too small for them. 2. We need to account for agent size when “funnelling” through the list of nodes returned by our A* search to obtain the actual shortest path. For problem #1, please see my full description and solution in this post from 2008. You will see that for each node, it is necessary to store a separate size restriction value for every edge-pair combination that an agent could enter and leave from. If our nodes are triangles, this means each one must store three separate widths. If we allow other kinds of convex polygons, then the number of widths each node must store will be equal to the sum of all integers from 1 to (number_of_neighbours – 1), if my brain is working correctly at the moment. We would need to come up with an equation to reference the right value from a node’s array of stored widths given an entry edge and an exit edge – this should be fairly trivial. For problem #2, please see my solution in this post from 2009, as well as my other contributions in the same thread. The linked post explains (my version of) the funnel algorithm and then explains the modifications that you need to make to account for agent size, providing pseudo code at both stages. Just let me know if you have any questions. On a side note, I obviously don’t think that the traditional solution of expanding and bevelling the base navigation mesh to account for agent size is very elegant. Apart from necessitating a new mesh for each possible agent size, it also increases the complexity of the navigation mesh at every concave feature. For fast pathfinding, we want to reduce the number of nodes that need to be searched, not increase it.
  13. Hi Gamedev.net! Years ago, I was an active member here and a very enthusiastic game programmer. For the better or worse, life took me in a different direction. I turned away from game programming and have spent the last so-many years studying history and foreign language. It occurred to me that I have, sitting idle on my hard disc, a fast and robust navigation mesh / path finding implementation based loosely on the Douglas Demyen Triangle-Reduced A* thesis (of which seems to have disappeared from the internet – only the shorter journal article is now available). It was part of a game I was working on years ago, was rewritten from scratch on at least one occasion. Rather than let that work go to waste, I thought I might turn it into a stand-alone C++ library that would be free for non-commercial use. Features: * Automated construction of navigation mesh (uses Triangle triangulation library). * Speed. The implementation is fast, primarily, because only triangles with three neighbours (“keynodes”) are included in the A* search. All other triangles are collapsed into “corridors” and skipped over. In most environments, keynodes account for 1/4 to 1/3 of all triangles in the navigation mesh. * A single navigation mesh is used to find paths for agents of any size – no need for duplicate navigation meshes. * It’s paired with a kd-tree system that has some bonus features that could be useful (very fast visibility + swept circle checks against navigation mesh etc). Shortcomings: * It’s simple-2D only – does not support overlapping areas or varying-cost terrain types, though the former could probably be implemented without a huge effort. * The navigation mesh cannot be dynamically updated. * I doubt I would be able to spend a lot of time developing it further. Here’s a few screenshots of the implementation finding some very long paths. Time estimates were recorded on my laptop – an Intel i5-2450 2.50GHz processor – in a standard Windows 7 environment, and are the average of 10 000 queries.   Search time: 0.041ms and 0.036ms. Navmesh: 772 triangles, 255 of which are keynodes (pink).   Search time: 0.039ms and 0.025ms. Navmesh: 820 triangles, 251 of which are keynodes.   Search time: 0.069ms and 0.056ms. Navmesh: 1213 triangles, 366 of which are keynodes.   Varying agent sizes pose no problem. Search time for each path: in the range of 0.006ms. It looks like the need for such a library has lessened due to the appearance of Detour, which didn’t exist when I developed it. In short, I’m just wondering if there would be any interest in this project? I can only really justify putting time into it if it looks like there might be some interest/communal benefit.   Thanks for reading!
  14. jacksaccountongamedev

    2D Top-down multiplayer-style shooter

    Hi Mybowlcut, thanks for playing. The camera actually does automatically follow the player after he dies. It just takes a few seconds to respawn, which is supposed to be punishment for dieing. The game usually has sound, at least for testing purposes. I just had to take them out before posting because they are all borrowed from Soldat. The AI has probably been the largest part of development. Although I started with multiplayer in mind, the game quickly turned into an arena for me to experiment with AI techniques. I'm pretty happy with the cat-and-mouse style combat that has been the result.
  15. jacksaccountongamedev

    How much do you trust Wikipedia?

    Quote:Original post by zyrolasting This is obvious now, but just to reiterate, some academic facilities suspect that Wikipedia is unreliable due to the fact that articles can be edited publically. In terms of academics, whether the information on Wikipedia is accurate or not is a secondary issue. You've already noted the more important issue: Quote: I suppose the real issue (again, probably just stating the obvious) is that people believe that the information on Wikipedia can change at any moment This isn't just something that "people believe," it is a true fact. If you are writing a research paper or any high level of academic work you are expected to cite your sources of information so that readers can trace that information to its sources. Regardless of its perceived quality, you can't do this with Wikipedia because the information you cite might not even exist the next day. Thus, it doesn't matter if 50%, 90% or even 100% of editors are considered "competent." For academic purposes, Wikipedia can't be used other than on an informal basis. The sources that Wikipedia cites, however, are often static texts - thus your school's encouragement for students to use Wikipedia as a "shortcut", or gateway to relevant texts on whatever subject. Quote: Isn't treating work like a "Links" page to more "trusted" (read: relevant) material kind of an eff-yew to competent contributors? Not really, for the reasons explained above. You'd be more interested in the "References" section, though. It's normally not difficult to tell which texts are things that you can include in your papers.
  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!