Brogramming

I've been slacking off on my project for the past few days. I've reached the point where the biggest bottleneck in performance is pathfinding on large maps, especially when pathing to the goal is not possible. As-is, it determines a lack of pathing when the whole available space's nodes are checked and the goal hasn't been found. For a 1600x1600 grid(a size I consider small for this project, since eventually I intend for infantry to take up three or four spaces), that translates to a LOT of wasted calculation time and lag.

I have a few ideas on how to make it more efficient, and not all of them are pleasant.

I thought I was done with that pathfinding, as mentioned. But during testing, I noticed that occasionally, it seemed to cease pathing to the goal halfway through. I discovered this while putting it through its paces, I created an obstacle course for it to path, a central barrier extending from the bottom left to the top right of the map, with smaller zig-zags between. Sometimes, I noticed, it would simply stop in the upper right. My first instinct was that for some reason the searching code wasn't able to detect new nodes in some cases.

No, that seems to be just fine. All the checks are in order.

Maybe dictionaries or arraylists have an upper limit on their content? Let's try making an extremely long and narrow course...

No, it's going through this entire thing just fine.

Maybe it's the smoothing algorithm? Perhaps it's cutting off nodes after a certain point.

No, the final node in the pathfinder matches the final node in the smoother.

Hm, maybe it just needs more nodes to work with, perhaps there are some exotic cases where it can't go around certain types of corners. Let's just have it place a new node every few steps, and...

...Nothing. That's not the case.

What the HELL is going ON!?

...

Uh.

Oh.

I just noticed there's an obstacle inside the goal marker.

Welp.

So, as it turns out, I'm an idiot. What was throwing me off was that, when it can't find the goal, it'll just path to whatever point is closest. Unfortunately, I never actually wrote that part of the code. My obstacle course is built  such that the halfway point is in the upper-right corner, and it was defaulting to the upper-right corner not because it was closest to the goal, but because it was FARTHEST AWAY, because that's the last node it checks before it decides it can't reach the goal. It couldn't reach the goal because I put an obstacle RIGHT where the goal is.

Hey, it works! Great.

After a couple days retooling my pathfinding algorithm AGAIN, I worked in that thread-pulling algorithm I mentioned earlier. The red line is the original path, and the blue line is the new one.

If I weren't making an RTS, this would be perfectly usable as a pathfinder for, say, a first-person shooter. Unfortunately, I'm an idiot and intend to work this into being usable for massive numbers of units.

Right now I only have a very vague idea how to do it:

find the center of a group of units

use this algorithm to set up a basic path from there to the intended destination.

create a flowfield along this route.

move units along this field.

Adding a flowfield might sound strange, but for local avoidance it will probably be my best bet. JPS, virtually by nature, is incapable of dynamic avoidance on its own. Flowfields, on the other hand, can be changed at will. I have some idea how they work. The thing I'm least confident about them is how to get them to interact with obstacles. Ideally, when a gridpoint with a flowfield vector points at an obstacle, it should turn it in the right direction.

There IS an alternative I can take, though:

Arbitrarily select a unit within a group as a 'commander' unit. This is the one that will follow the path.

Using a flocking/boids algorithm, have the other units follow the commander closely.

The advantage to this is that I can worry less about the amount of overhead a flowfield will create. The idea is that each unit simply takes note of the direction, location, and velocity of the units immediately surrounding them and adjusts to move with them.

One thing I still need to think about is how to prevent units from following these paths through areas too small for them. It would be unseemly for a tank to walk through a door. Right off the bat I think that maybe each unit of a given size has its own commander, and each of those simply goes as far as they can given their size.

That was easier than I thought it would be.

At first I assumed I was going to have to get involved with trig or raycasting line-of-sight bullshit, but I worked out a way to do it with some relatively simple logic and VERY simple math. That's good, it should save me a ton of overhead.

I still have to work this into the actual pathfinder algorithm, but that should be relatively easy. All this does is generate a series of grid points between two nodes. Using that data I can simply check to see if any of those points contain an obstacle. If not, then I'll be able to clip a node that would otherwise lay between these two points.

I figure by starting with the two nodes at either end of a path and then working doing a nested for() loop, I'll be able to sweep the node path and find some nice shortcuts. Mostly all of this is to make units traverse the map in a more natural-looking fashion. With JPS you're working on an orthagonal grid, so nodes will start off at 45 degree angles from each other.

After several attempts and at least as many days, I have an algorithm that returns a list of points that lead to a destination.

Hoo-fuckin-rah.

Over the past few days, I've explored how scripts interact with object that they're stuck in, how child objects can be accessed and how they behave... and that's about it. I wrote some pathfinding code, but I hadn't implemented units so I couldn't test any of it as I went, which was a mistake. So, that's where I'm starting.

I've attempted to use unity's GetComponent script many times, and I still don't understand what it demands of me. It's completely unintuitive, and it gives very generic error messages. I found some code online where someone managed to whisper it into doing what I wanted, so I borrowed that line. Considering it was on Stack Exchange, I don't think they'll mind.

In my latest project, I'm experimenting with building game objects modularly. I have a generic RTS object whose script holds some basic values, then I stick scripts into the same object to customize what I want. I have a visualizer script that creates an arbitrary mesh on the object which will work for depicting the base script's size value, for example. I can write scripts which will create controller functions, or attack functions, health data, what-have-you.  I'm optimistic about this approach.

I think John Carmack made the case that eventually programming would grow so complex that black box coding would be the only way to accomplish anything. It certainly helps ME keep things organized.

That's working pretty well.

You may notice that there are some numbers that are above 1 that are directly next to obstacles. That's expected. This particular algorithm functions on the idea that you find the spaces using squares that expand outward in one direction. You make this work by having each unit pathfind from one of its corners instead of its center. The net result is the same. Plus you can punch out this code in about ten lines, which is always nice.

I do see a small bug, though. For values close to one side of the grid(two or fewer spaces away) it doesn't adjust the values correctly. As much as I'd like to make something flawless, I can't seem to track down that particular bug, and it probably won't affect anything anyway. The gamespace will almost certainly be smaller than the arena that's built around it.

After some time fiddling with tutorials and hammering code into shape, I've got the first steps towards what I intend to do.

What you're seeing here is a visualized array of values. The black squares represent values of zero on the grid. The negative one values are spaces that have not been assigned a more appropriate number.

"What the hell is this for," you may ask. Well, in pathfinding, sometimes you need to accommodate units of varying size. Larger units shouldn't follow the same path as small ones or they'll clip through the obstacles they should be avoiding. To fix this, one sets each gridpoint a value equal to its distance from all obstacles. Then, larger units simply use the larger values to path.

I don't yet have an algorithm for this, but that's what this is all for. It will help me see my code working once I actually get it in there.

I'm nothing if not a grid-generating fool.

In this case, this gentleman didn't seem to be aware of constant values or that it's not efficient to declare variables in a repeating function.

Let's go back several years.