• Content count

  • Joined

  • Last visited

Community Reputation

173 Neutral

About Crayz92

  • Rank

Personal Information


  • Steam

Recent Profile Visitors

2064 profile views
  1. Seek, separation, and neighbor avoidance. The agent gets stuck when its path runs between 2 obstacles which are perpendicular to the path and distance between the 2 obstacles is less than the agent's radius. The agent ends up in an endless loop bouncing between the 2 obstacles rather than steering around them intelligently. The problem scales when there are even more agents/obstacles placed in such a manner
  2. I'm having a difficult time coming up with a local avoidance strategy for my agents. My problem is pathing/steering around stationary units in a semi-intelligent manner. I've recorded a quick demonstration of the problem here: And here's a demonstration of ideal behavior: The movement of units is pretty smooth and directed, so it would suggest they perform some sort of path planning rather than steering. Steering also seems to be documented mostly for groups/non stationary agents. I know that Dota 2 uses a square grid to perform pathfinding, but the movement of these units is precise and not aligned to the grid, so there much be some other algorithm that takes into consideration nearby units and constructs a simple path to reach the destination. I'm having a hard time figuring out how this could be done. Things I have tried: 1. Flagging nodes on my square grid as Occupied - during pathfinding search occupied nodes are treated as unwalkable. works, but it's a headache trying to get agents to move smoothly and introduces a handful of other problems, i.e. targeting a unit that is completely surrounded, keeping agents aligned to the grid 2. I tried adapting the bug algorithm in a way that works with agents as obstacles. While an agent is moving along its path and colliding with another agent, it scans neighbor nodes for walkable space, inserts the best neighbor node to its path, and moves towards the new node before continuing to move towards the goal. Sort of works, but it causes agents to move back and forth quite a bit as they progress towards the goal again only to find that there's another collision in the way. There are also some cases where the agent gets trapped because it fails to backtrack or work around maze like situations. 3. Steering. As seen in the first demonstration video, steering has some limitations that I don't know how to work around. I've thought about treating groups of stationary units as one single obstacle and implementing obstacle avoidance steering vs polygons, but I'm not sure how to go about that, or if it will end up being optimal and/or efficient, and forming proper polygons seems like a daunting task when my agents have a variable radius. 4. Local proximity pathfinding search - find points around all nearby agents and perform a search against those points. I haven't implemented or tested this idea yet, it doesn't sound much better than using the map's actual pathfinding grid with Occupied (unwalkable) nodes marked where agents are standing. Is there a standard solution? Maybe it's a trivial matter and my overthinking/stress is causing me to see past an easy solution.
  3. Thanks for the discussions, they've gone towards improvements in my code and understanding of pathfinding. Now I am having problems with local avoidance but that's a problem for another thread
  4. I decided early on to avoid Unity as much as possible and keep all my game's logic within its own boundaries. Reason for it is so that my server can run headless and/or standalone with no dependencies to Unity. And reinventing the wheel isn't such a bad thing, if I had decided to stick to Unity's physics and pathfinding I would only have a little bit more knowledge about Unity and a lot less knowledge about pathfinding and physics.
  5. I went over my code and found some issues - kind of funny how the heuristic I was using showed better performance with a bug in the A* algorithm. It's overall better performance now using the diagonal distance heuristic. Yea, definitely a lot of overhead from the profiler. I use it just to get an idea of where things are at. I am on Visual Studio, I wonder if its possible for it to hook into the Unity editor and profile that way? I fixed up my JPS algorithm as well, it shows about 15-20% increased performance but in some cases performed much worse, so I'll have to do some more digging.
  6. I have my debug script set up just like that The results in the two screenshots above are from this Stopwatch snippet with deep profile & profiler disabled completely
  7. I've played around with a variety of heuristics, this is the fastest I've come across and it produces acceptable results. I'll give JPS another try, it's very possibly my implementation is messed up. Ah I didn't mention that profiler screenshot is the result of 100 paths in a single frame. Here's a better shot for a single path: I fixed up some code and gave Manhattan distance a test run. Here's a comparison between my current heuristic & Manhattan Manhattan without weight puts it at about 2,200ms. While Manhattan makes for a better looking path, post-processing takes care of that so I'm mostly interested in speed
  8. I have. The two biggest bottlenecks are in point reduction and the priority queue (using BlueRaja's which claims to be the fastest) Here's a screenshot from the Unity profiler: Profiling alone adds a lot of overhead but I think it gives a good idea of where things sit. I've never used a profile other than Unity's
  9. Here are the two main files: Path: AStar: A few things I've done to optimize the search: 1. Rather than a dictionary to keep track of scores and parents, I use a 2d array of objects that are mapped to the grid i.e. [x,y] represents grid point (x,y). Objects have F,G,H and Parent fields, these fields are reset to default values during each search. 2. Cheap weighted heuristic 3. Orthogonal neighbors (searching 4 neighbors rather than 8) Paths don't have to be beautiful because the point reduction smooths them out quite nice. In Path.cs you can see the two functions to reduce points, Incremental and Stretch. Stretch is much faster because it has the potential to reduce points all the way to the end right off the bat or early on thus reducing calls to the LineOfSight function, but it isn't so reliable around small areas/corners. The incremental function is reliable but it calls to the LineOfSight function for each and every point along the path, this causes the path reduction to be just about as slow as calculating the path itself. Line of Sight is determined by getting all points between 2 points and checking that they are all flagged as Walkable. My grid is dynamic and roughly 250x250. I tried out Theta* and JPS, both were slower than my current A*. I'm trying to avoid using a navmesh or worker thread, I suppose mostly just looking for ideas to tighten up my code
  10. My grid agents will flag the node they are standing on/moving to as Occupied and I've implemented an option into my A* that basically says Occupied nodes are unwalkable and skips them during the search much like it would a node marked as unwalkable/wall/etc. It makes for somewhat boxy movement much like Warcraft 3 or the original Starcraft I suppose. Since paths are calculated on a single frame I can't determine what nodes might have changed and become occupied after an agent has already calculated a path, so if a node along the agent's path becomes occupied after the fact he will walk right through it. To counter this, in my update loop (if the agent is currently moving) I determine what node the agent will be standing in next, and if it's occupied the agent will stop, stall for a brief moment, then calculate another path. I recorded a quick video to show what this looks like:
  11. I first learned with NLua - I believe there is a lot more documentation and discussions for NLua so it's an easier one to learn. It took me a few months to get a grasp on using NLua and the Lua language itself, but I started exactly where you're at now with a few simple samples. It just took some time
  12. A massive amount of labor and resources are required to create a fully fledged secure multiplayer ARPG game. As the solo developer behind Project Peril, I'm looking at another year at least before there is a genuinely decent playable product. Project Peril has been in development for 12 months. I am quite proud of the work that's gone into it, but unfortunately I can't continue working in the dark. Therefore, Project Peril has been postponed. I am taking the functional code-base of Project Peril and using it to create a new game that I hope to have a playable prototype of by November. The idea of this new game is to receive publicity and funding which will ultimately allow me to pick up where Project Peril left off and hire a team of developers to put together a real studio. If this new game happens to succeed then it may become my primary focus of attention. More information on my new game will be announced in the following weeks. If you enjoy my blog please check out my Facebook page where I post the same weekly blog plus an occasional video or screenshot.
  13. I found it by accident, can't remember what exactly but I googled a line of code that was in XLua's source somewhere and it popped up in the search results.
  14. There hasn't been much for new features lately since I've only been refactoring, so I whipped up a couple videos to showcase in better detail a few of the old features I have coded into Project Peril. Dungeon Generation: Entity Activation:
  15. [Project Peril] Master Servers

    During the process of refactoring my network code I realized that my clients are connecting to only one server, and this one server has no outlet to any other servers. This means that players would only be able to chat and play with other players who are connected to the same exact machine. This is obviously a problem if I intend for my game to support a lot of players across multiple regions. So I began writing code for master servers. There are now 4 different servers each with their own independent process: Login, Lobby, Game, and Master Lobby. The lobby server will receive packets (i.e. ChatMessage) from clients, then relay that packet to the Master Lobby server which then relays the packet to all Lobby servers in a region who then relay the packet to any clients they are connected with. Similar behavior will be put in place for requesting a list of games – the client asks for a list of games in a specific region, the Lobby server relays the request to the Master Lobby server, the Master Lobby server then tells all game servers in that region to send their games to the client. I’m no expert in networking and this is all a big experiment, I’m not sure how well this is going to work out in the long run. If it doesn’t work then it’ll be a lesson learned and I’ll be rewriting the networking code all over again. The refactoring process for Login and Lobby servers is just about done. I can move onto gameplay pretty soon and begin implementing fancy networking models and re-creating all the gameplay interface to support the new HTML system. If you like my blog please consider following on Facebook where I post the same weekly blogs and an occasional screenshot or video.