Find nearest object on a path?

This is more of a general question.

Suppose I have a grid with walls. I have several objects within the grid. What's the best way to find which object is closest to another object based on path and not distance? I can't use the distance function because the closest object (based on actual distance) may not be the closest object due to walls, and another object may actually be 'closer' based on path.

Does anyone know of how I might accomplish this?

I haven't tried it so this is just a thought, but maybe you can use the nodes in the path finding, have you tried that?

Can you elaborate a bit more on how I would use nodes?

If you have your tiles saved in an array, you could work with that, identify adjacent tiles, add them to another array and check those adjacent tiles for objects.

the other array could look like this:

each x -> one tile

y=0: x coordinate in tile-array

y=1: y coordinate in tile-array

y=2: status (0 = searched for object, 1 = searched for adjacent tiles)

okay let's say you are at a junction at 5,5. You run your function.

The function will return

(4,5), (6,5), (5,4), (5,6). It didn't find an object, so it will look further. For each x in the array where at(curx,2) = 0 -> run the function again.

The function should only add coordinates if they are not already in your array (to prevent from going back, searching fields twice). After every adjacent tile was checked for (4,5), its y2 is set to 1.

The search/loops are stopped once an object was found or no new adjacent tile was added to the array. After that the array is cleaned up (set size to 1,1,1 I guess).

Can you elaborate a bit more on how I would use nodes?

When path finding create a path it create nodes along those path, kinda like waypoints. You can get the position of these, which you can then use to do your tests.

As I said, I haven't tried something like what you are trying to do, so whether it works or not I don't know.

But here is a simple test of what it looks like. The green squares are nodes.

Just so you know sometimes the nodes aint showing, think that is because its probably trying to reach a point under a solid or because I made it really fast and there are a bug in it <img src="smileys/smiley36.gif" border="0" align="middle">

But you should still be able to see what I mean....I hope :D

Path finding node test

If you have your tiles saved in an array, you could work with that, identify adjacent tiles, add them to another array and check those adjacent tiles for objects.

the other array could look like this:

each x -> one tile

y=0: x coordinate in tile-array

y=1: y coordinate in tile-array

y=2: status (0 = searched for object, 1 = searched for adjacent tiles)

okay let's say you are at a junction at 5,5. You run your function.

The function will return

(4,5), (6,5), (5,4), (5,6). It didn't find an object, so it will look further. For each x in the array where at(curx,2) = 0 -> run the function again.

The function should only add coordinates if they are not already in your array (to prevent from going back, searching fields twice). After every adjacent tile was checked for (4,5), its y2 is set to 1.

The search/loops are stopped once an object was found or no new adjacent tile was added to the array. After that the array is cleaned up (set size to 1,1,1 I guess).

This makes sense. I'm using a recursive function to do this, but I think I've created an endless loop, because the preview tends to crash.

<img src="http://i.imgur.com/z31L2q1.png" border="0" />

The values in the BoardSpaces array contain the UID of the grid tiles. It's -1 if it doesn't exist.

<img src="http://i.imgur.com/rjuv2OV.png" border="0" />

My goal is to have the function recursively loop through the squares until it finds a player object, in which case ComputerTarget is set to that UID and the function should stop running. However, in my testing I get an endless loop and the program crashes.

Here's the .capx if anyone has the time to take a look. The .capx as a whole is pretty complex, but the relevant part is shown in the screenshot above and most of the events are commented.

BoardGame.capx

Excal,

I do not want download your file or analyse your code, because it can be simpler than you're thinking...

First of all, distance is a trick if you're dealing with a non static object.

But, I did the job by using instance variables, setting the objects who need to be checking against another object by storing their "Distances" inside this instance variable, then, pick the object with the higher/lower "Distance".

So:

= Every tick:

= For each Obstacle:

-> Set instance variable "Distance" to [distance(Player.x,Player.y,Obstacle.x,Obstacle.y)]

= Pick lowest "Distance" from Obstacle:

-> Do whatever you want...

Avoid making objects with the same exactly distance, or, the system will sort one of them...

If it's not possible, simple make an index, so, put inside the "Distance" a dot and plus, an index, like the IID or UID, and the system will always pick the objects with the same distance, but will select the smaller IID or UID or another instance variable, like ID, its your choice...

TELLES0808, I think a big WHOOSH just happened.

My first post explains how I cannot use the distance function to do this.

TELLES0808: it is about distance along the path, not linear distance.

Excal, can you re post the link to your CAPX? The current link is broken.

makotto, here you go: BoardGame.capx

mindfaQ, I noticed after posting, thx!

Excal,

I did a sample a time ago, for a friend, and may it match perfectly for you.

It's using pathfinder, but it don't will make any difference for you, but will make possible to check the distance.

dl.dropboxusercontent.com/u/47035927/Samples/Path_Distance_Demo.capx

Enjoy...

Edited:

Ashley, I would like ask you if is possible to implement a new function inside the pathfinder behavior?

Please, consider making a "travel distance" or something similar, so, we will be able to check the shortest and longest paths and improve our AIs.

I think most of the users needing it will not achieve workarounds like on the sample above.

How about calculating waypoints between each pathfinding node, and finding the object closest to a waypoint:

Demo

Click any whitespace to start pathfinding.

The closest object along the path will grow/shrink.

Capx

It's not precise, but it's an extremely close approximation.

zatyka, I think the issue here is the assumption I have a pathfinding object that is moving.

Since I am trying to find the closest object that can be pathed to, I would probably have to path to all four corners of the board to determine which object is closest along any path.

Running a pathfinding object four times will take time (possible noticeable game lag) and CPU :(