Getting closest tree, with a twist

I have a spell that creates a unit inside a forest and has it move to the caster.

At the moment, it works as follows:
1. Find nearest tree to caster
2. Create unit
3. Turn unit pathing off
4. Move unit to tree
5. Order unit to "smart" caster
6. Wait 2 seconds
7. Turn unit pathing on

For the most part it works great, however if the caster is too close to the tree then the new unit will stop, still inside the trees, and then 2 seconds later will jump to the nearest pathable point (which could be inside the forest completely surrounded by trees).

What I want to do is have the unit spawn at the nearest tree that is also a minimum distance away from the caster AND has no further trees between the chosen tree and the caster.

I've been looking at different ways of determining the correct tree but can't seem to find a solution that works regardless of the configuration of trees.

Alternatively, if the unit actually respected pathing i.e. moved to the nearest pathable point before "smart"ing the caster that would be ideal - but obviously a unit with pathing turned off doesn't respect pathing.

Any ideas?

What function are you using to find the nearest tree? This might be easily fixed with a well placed condition, but we need to know how you're coding it in order to help you the best we can. Also, are you using GUI or JASS?

Plain JASS.

For getting the nearest tree I'm just enumerating in an area and calculating distance between tree and caster for every tree.

One thought that just occurred to me was to find the biggest rectangle that contains the caster without containing any trees, then increase the size of that rectangle by 64 in each direction, enumerate the trees picking the first closest tree that is further away from the caster than the minimum distance... but no idea how to find the largest rectangle that contains the caster and no trees.

If you center the rect, or whatever you're using to find the closest position of the tree, just add a condition that the width and length of the rect are a certain value before it starts accepting any trees.

edit: I missed the part where you said you need a direct path between the picked tree and the unit... that's going to be a bit more tricky. I thought you just wanted a minimum distance on it.

Grouping units(anything) in a rectangle would require many sin/cos calls and end up being inefficient. You're better off doing something like:

Psuedocode:

I don't remember who first came up with the idea to do this, but it's not my idea. Anyways it should work fairly quickly, it just checks the greatest squared hypotenuse (divided by some large abstract number so it doesn't switch signs) agenst that of others and returns the best result. If you need the actual distance return the destructable and calculate it using atan2(casterY-destrY, casterX-destrX) as you don't want to be using atan in a loop if at all possible.

That's fairly close to what I'm doing now:
set cur = SquareRoot(dx * dx + dy * dy)
It's only over a rect 2048 in each direction so not causing any problems, at least for me...
But that gives me trees that are in the middle of the forest, not on the edge of the forest closest to the caster.

Yeah that's the part that's got me stumped. It's only because there has to be enough space between the 'summoned' unit and the caster for it to emerge from the trees and stop just short of the caster, and the summoned unit has no pathing so will take a straight line path to the caster.

Aren't there systems that can check pathing? Maybe create 2 dummy units, one that shoots a projectile really fast that gets blocked by trees, and if it hits the second dummy unit then it's a straight shot. If not, then you know there's a tree there.

Finding the nearest tree to the caster that is outside minimum range and is positioned so that a line between it and the caster goes only across pathable terrain apart from the tree's pathing is complicated, but it's not even the trickiest part. The tricky parts are a)what if such a tree does not exist and b)what if the caster moves while the unit is approaching him in such a way that the unit ends up on unpathable terrain when it's pathing is enabled?

I think you're better off creating the unit at the nearest tree and finding a different way of adressing your issue (for example, after the wait, if the unit is still within the pathing square of the tree it was created at, wait some more) than if you persist with this unwieldy algorithm.

It's returning an object in the middle of the forest? It should always return the closest tree, or do you mean it's returning a close tree that does not fit your needs? Also, the reason I use the method above is because SquareRoot is just awfully slow.

But your criteria is, well it's preposterous. You might want to try finding a tree, finding the distance between the trees closest to it, and creating the unit at the point where the greatest gap exists. If you truly needs it to be in a triangle, you could make a rect that enumerates all destructables in it, then move it downwards and shrink it's X. It's worlds more efficient then evaluating a bunch of atan2's however it's still not a very good alternative. To add to that, finding a path which exists between trees and the caster in a straight line is not going to happen. The odds of this event happening get worse as the terrain gets prittier, as a result a very nice map will never evaluate the correct criteria. Well, the criteria will almost never evaluate anyways. You definantly need to rethink that part.

You are, of course, right. I think Anitarf's method is the best.
I'm thinking every 0.5 seconds, if point unit is standing on is pathable, no destructibles or units within some distance, then turn pathing back on.

Not sure what circumstances IsTerrainPathable returns true/false though...

It ignores destructable pathing, but takes into account cliffs and doodads, so yeah, you'd need to look for both destructables and units in range; but instead of doing that I suggest trying to move an invisible dummy unit there with SetUnitPosition (which takes pathing into account; it might not work if it still considers your unit as a pathing obstacle despite it's pathing being disabled, though, I'm not quite sure how that works; in that case you'd need to do it differently) if that unit's coordinates after the move match the coordinates you tried moving it to then that point is pathable and you can remove the dummy unit and turn collision on for your dummy unit.

Thanks guys, works awesomely now.

Every 0.5 seconds
1. Check terrain is pathable
2. Check zero doodads in 256x256 rect centered on unit
3. Check zero units in 256x256 rect centered on unit (not counting the unittype of the unit)
If all 3 conditions satisfied then turn pathing back on.

Works like a dream!