ID:1946170
 
(See the best response by Ter13.)
Code:


Problem description:

I want to create a move proc that moves to a target while avoiding certain others. To accomplish this I though of increasing movement cost around the targets I want the unit to avoid. So my pathfinding algorithm will search for prefer different paths. Is this a good aproach or there is a better way??
Best response
To accomplish this I though of increasing movement cost around the targets I want the unit to avoid.

That sounds reasonable.
Ok so I was asking the obvious...
I just get an increase in cpu usage and thought there would be another way. Anyway thanks for helping
Unfortunately, that's kind of the nature of A*. It's not exactly highly efficient.

How are you modifying the heuristic based on the distance?
I don't modify it it just returns the distance :)
Should I create different heuristic for short and longer distances??

It seems I need to do more research on optimizing my code. That's the difficult thing with programming, you don't only have to make it work, you have to make it good :)
IMO, this is something that really shouldn't be focused on because there's not going to be an optimal solution.

A* pathfinding already suffers from an exponential complexity rating. At the very best case scenario, you are looking at multiplying an exponential complexity rating. If you are using an optimal approach, you'll be multiplying it by a constant. If you are using a suboptimal approach, you'll be multiplying it by potentially another exponential complexity.

Like I said in the last thread: Tunneling down ideal pathfinding solutions is a fast way to kill a game project. Focus on gameplay. Don't worry about pathfinding until last, and definitely don't focus on refinements to pathfinding like this one until you have a playable game.
Ter is right. But if you want a headway for modifying a pathing system to avoid certain atoms, work with orange() and use some kind of estimating function to determine if the new location will be too close to any atoms to be avoided. It's things like this that make me wish we could go in and change hard-coded processes, like the default pathing.

EDIT:
Disregard my advice.
Actually, orange() is terrible advice.

To know the distance between two objects, you don't need to get every atom in range. orange() is insanely slow and should never be used with an A* implementation.

You need to remember that each pathing operation will iterate over potentially millions of turfs. Calling orange() millions of times will be a problem.
What would a better way be? I imagined just using a for loop to check atom types in orange().
Although, I suppose in the spirit of actually answering the question, one way to cheap out on this would be to pre-cache turfs within a specific arbitrary range of all the targets before doing node-traversal. Pseudocode follows:

proc/orange_block(atom/o,rng)
. = block(locate(max(o.x-rng,1),max(o.y-rng,1),o.z),locate(min(o.x+rng,world.maxx),min(o.y+rng,world.maxy),z) - locate(o.x,o.y,o.z)


var/list/mod_heuristic = list()
var/len = avoid_targets.len
var/atom/movable/o
var/list/blockturfs = list()
var/list/tl
var/len2
var/turf/t
var/ox
var/oy
var/oh
var/nh
for(var/count in 1 to len) //loop through each target to be avoided
o = avoid_targets[count]
ox = o.x // cache x and y for less look-ups down in the next loop
oy = o.y
tl = orange_block(o,AVOID_RANGE)
len = tl.len
for(var/pos in 1 to len2) //apply the turfs in range of the avoid targets to the heuristic list with a distance heuristic
t = tl[pos]
nh = abs(t.x - ox) + abs(t.y - oy) //the new heuristic for this tile
oh = blockturfs[t] //if an previous heuristic exists for this tile, this will be non-null
if(!oh||nh>oh) //make sure that the previous value isn't greater or equal to the new value or there is no old value
blockturfs[t] = nh //associate the tile with the distance from the target


What this does is create an associative list of tiles which you can then test against for pathfinding nodes to modify the existing heuristic. During your node exploration phase, you should be sorting your pending node investigations based on the multiplication of this new heuristic and the distance to the target. Normally, I'd argue that you shouldn't precache data in a pathfinding solution like this, but in this case, not doing so is going to mean you have to iterate through every single target and determine a distance for every target for every node investigation. This means if you are searching for a long path, you'll come up with significant savings. On the other hand, if you are searching for a short path, you will wind up wasting a lot of cycles assigning the heuristic to each tile near each target to be avoided.
In response to Konlet
Konlet wrote:
What would a better way be? I imagined just using a for loop to check atom types in orange().

I'm not saying this to be mean, but Konlet, what's your understanding of A* pathfinding? Are you familiar with what a heuristic is? Are you familiar with the differences between D*, A*, and LPA*? Do you know what a quadtree is? Do you know what a navmesh is? How about Theta*?

If you are coming up blank on any of these questions/topics, this thread is probably one you aren't likely to be able to help with. I'm not telling you that you shouldn't try to help others. I commend the effort. But this is one of those threads that's going to be way out of your depth. Pathfinding is a CRAZY topic and can take years to master. It's one of the very few places where you wind up iterating over millions of nodes per operation and it's considered totally acceptable. So super-optimal approaches are all but required. This is one of those threads where: "yeah, but my way works" is totally not an okay answer. This is one of those areas where efficiency is actually of concern, and microseconds matter.

Again, if I'm assuming too much, correct me, but... I did my homework on your recent library. I think I'm correct in assuming you aren't quite where you need to be to be contributing to this topic in a helpful manner.
In response to Ter13
You're completely right. I'll make it a note and study, thanks for the advice; sorry for the misinformation, just one of those things that I simply didn't know there was more to.
I do want to apologize again, in case you think I'm being at all rude or dismissive. I went ahead and offered my CC on that library I mentioned I looked at to gauge what you knew as well, since I didn't want to seem like I was kicking you out of a thread or anything. I hope the CC helps for that saving library you made so far. You should be able to learn a lot from my writeup. I really really don't want you to think that I'm trying to be mean at all. It's just that I spent the better part of 2 years pounding my head into the wall that is pathfinding algorithms and optimization techniques and I'm still not quite sure I'm good at it.

Several PHDs have spent their entire working lives playing with pathfinding techniques and still haven't found very satisfying solutions to the problem. This is one of those areas of AI programming that's been at a major standstill for decades. It's so vexing too, because humans can intuitively do it with zero effort sometimes faster than a computer can.
I didn't use orange to find neighbors either. Ok checked the path finding and movement and it works smoothly. Checked it with 20 mobs and does not lag at all. I haven't optimized long distances yet though. And I will take your advise Ter and work on the game first.

So now about collision checking. For events that I want to occur when to mobs meet(one is trying to move through the other) I should use Crossed,Entered,Cross or Enter ???
I would guess Crossed but want to be sure.
And if someone could give me a brief explanation of how Exit/Enter differs from Cross/Crossed
In response to Ter13
I think one of the problems with their design choices (concerning AI programming and path-finding) is that they allow the computer to attempt to calculate too many paths at one time. One reason (that could be considered a good thing, we don't really want sentient AI...do we? Skynet is already on its way...) it is taking so long is because of the millions of different approaches available that the computer must select through but the human simply reacts. The human doesn't have to mark and calculate density, all of that work is done in real time via the organic computer, the brain! The computer spends too much time deciding what path (and if there is redundant code such as "if pathway blocked retry 5 times" makes the AI look stupid as it runs into walls, that isn't a cognitive solution to being blocked; it should instantly set that its path is blocked and lay paths around it in opposing directions and instantly select what isn't blocked, no redundant code) it ends up with all of those units in RTS games being cluttered together on hills or the AI bots in FPS games running into walls. The problem with AI path-finding design is that the designers/developers aren't focusing on a precognitive approach and instead are focusing on the usual reactive approach (which is always least effective in a proactive situation).
In response to Victorqr
Enter() and Exit() are meant to determine whether or not an object can enter or exit something. Entered() and Exited() are called after you have entered or exited something.

Same deal with Cross() and Crossed(): Cross() determines if an object can cross over another one, and Crossed() is called after you cross over it.

With that said, if you're working with turfs then you're going to want to use Enter[ed]() and Exit[ed](), and with objs and mobs you're going to want Cross[ed]() and Uncross[ed]().