# Crayz92

Member

49

173 Neutral

• Rank
Member

• Website
• Role
Programmer
• Interests
Programming

• Steam
taaz

## Recent Profile Visitors

3088 profile views

1. ## 2D character artist (sketch blog)

Hey Discord says it's invalid. Could you add me? Crayz#2326
2. ## 2D character artist (sketch blog)

I like a few of these characters, I think they would fit well in my Fallout/Wasteland inspired project. Would you like to work together?
3. ## Inconsistent interpolation velocity, and interp + lag compensation?

Useful article, but not related to networking. I fixed up my interp logic a bit. Had some issues with how I was finding the next frame to transition to, and processing the same position twice (t=1, then t=0 after finding a new frame), however still curious about lag compensation.
4. ## Inconsistent interpolation velocity, and interp + lag compensation?

My interpolation is having some jitters, and I think I've boiled it down to an inconsistent velocity based on the distance of point A to B. Is there a standard way of ensuring my interpolations are consistent? I'm not performing any sort of extrapolation, but I feel that might be the key, I'm just struggling a bit with the actual implementation of it. Here's my code, called every frame for every entity: var nextFrameIdx = GetFrameInPast(interp.Frames, 0.1f); // no available frame if (nextFrameIdx == -1) { continue; } var frame = interp.Frames[nextFrameIdx]; var ent = (NetEntity)hm; if (nextFrameIdx != interp.nextFrame) { //Debug.Log("------------------------------"); interp.fromPosition = pair.Key.Model.Position; // current rendered position interp.fromAngles = pair.Key.Model.Angles; // current rendered angles interp.toPosition = frame.Position; // state received by server interp.toAngles = frame.Angles; // state received by server interp.velocity = frame.Velocity; // state received by server interp.nextFrame = nextFrameIdx; //interp.accumulator = 0; interp.startTime = Time.time; interp.finishTime = Time.time + updateRate; } Debug.DrawLine(interp.fromPosition, interp.fromPosition + Vector3.up * 2, Color.green); Debug.DrawLine(interp.toPosition, interp.toPosition + Vector3.up * 2, Color.yellow); //interp.accumulator += Time.deltaTime; //var t = interp.accumulator / (interp.finishTime - interp.startTime); var t = (Time.time - interp.startTime) / (interp.finishTime - interp.startTime); //Debug.Log(t); var newPos = Vector3.LerpUnclamped(interp.fromPosition, interp.toPosition, t); var newRot = Quaternion.Lerp(Quaternion.Euler(interp.fromAngles), Quaternion.Euler(interp.toAngles), t); hm.Model.Set(newPos, newRot.eulerAngles); And here's how it looks, with an update rate of 2 per second: You can see movement velocity varies depending on how far the entity must move. With a smaller update interval, this becomes less obvious, but there are micro-jitters which I'm looking to get rid of. My other question is about lag compensation. In my code, each entity has its own accumulator or subframe for interpolation. Do I have to interpolate all entities simultaneously between global snapshots in order to send the client's subframe to servers to achieve an accurate rewind? edit: Here's a video showing the jitter at various update rates. Maybe its unrelated to my initial problem? More update rates gives pretty consistent spacings between point a & b https://streamable.com/72s2d
5. ## Local avoidance/steering vs. stationary agents

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
6. ## Local avoidance/steering vs. stationary agents

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: https://vid.me/5VvF4 And here's a demonstration of ideal behavior: https://vid.me/LTuHi 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.
7. ## Out of ideas for optimizing A* search, got any?

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
8. ## Out of ideas for optimizing A* search, got any?

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.
9. ## Out of ideas for optimizing A* search, got any?

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.
10. ## Out of ideas for optimizing A* search, got any?

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
11. ## Out of ideas for optimizing A* search, got any?

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
12. ## Out of ideas for optimizing A* search, got any?

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
13. ## Out of ideas for optimizing A* search, got any?

Here are the two main files: Path: https://pastebin.com/ZkrbJ78t AStar: https://pastebin.com/EVGazFtU 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
14. ## Is A* good when entities should collide with eachother?

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:
15. ## XLua - Tencent's Lua programming solution for C#

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