[VB6] X-Y search algorithm, help please!

[azkanan]

Situation

My game's world is made of Areas. In these areas are locations. (ie, an area might be a city, where the locations are churches, houses, malls, etc).

I need an algorithm that is used when trying to find the nearest locations. That is, if the player has started out with only knowing the location he is at, there is a button that the player can hit to search the immediate space about his location for new locations to travel to.

Every location is assigned a random X variable and Y variable.

As a result, I need an algorithm that will search within 3 "X,Y" spots in all directions of the player's location for any other locations, then I need to list these.

[](http://www.freemmorpgmaker.com/files/imagehost/#87c5ea5349cd954283e904cad9b44ced.png)

**Where Black is the Point of Origin.**

**Where Blue is the search area.**

**Where Green are the found locations.**

**Where Red are the unfound locations.**

[azkanan]

This is what I've come up with so far…

```

Dim SearchXMin As Integer

Dim SearchXMax As Integer

Dim SearchYMin As Integer

Dim SearchYMax As Integer

Dim SearchX As Integer

Dim SearchY As Integer

Dim NewPlace As Boolean

Dim Index As Integer

Dim Index2 As Integer

Dim Index3 As Integer

Call FINDPLAYER 'Assigns VarArea and VarLocation public variables to the player's Area and Location.

'Search Parameters

SearchXMin = Area(VarArea).location(VarLocation).x - 3

SearchXMax = Area(VarArea).location(VarLocation).x + 3

SearchYMin = Area(VarArea).location(VarLocation).y - 3

SearchYMax = Area(VarArea).location(VarLocation).y + 3

'Search Start Location

SearchX = SearchXMin

SearchY = SearchYMin

'For for each location in the area,

For Index = 1 To Area(VarArea).maxlocations

'And for each X...

For Index2 = SearchXMin To SearchXMax

SearchX = SearchX + 1

'...Search each Y

For Index3 = SearchYMin To SearchYMax

SearchY = SearchY + 1

If Area(VarArea).location(Index).x = SearchX And Area(VarArea).location(Index).y = SearchY Then

Area(VarArea).location(Index).Found = True

End If

Next Index3

Next Index2

Next Index

```

[azkanan]

On the upside, this piece of code is finding and displaying locations. On the downside, it seems to be duplicating them in my List.

```

Dim SearchXMin As Integer

Dim SearchXMax As Integer

Dim SearchYMin As Integer

Dim SearchYMax As Integer

Dim SearchX As Integer

Dim SearchY As Integer

Dim NewPlace As Boolean

Dim Index As Integer

Dim Index2 As Integer

Dim Index3 As Integer

Call FINDPLAYER 'Assigns VarArea and VarLocation public variables to the players Area and Location.'

'Search Parameters'

SearchXMin = Area(VarArea).location(VarLocation).x - 40

SearchXMax = Area(VarArea).location(VarLocation).x + 40

SearchYMin = Area(VarArea).location(VarLocation).y - 40

SearchYMax = Area(VarArea).location(VarLocation).y + 40

'Search Start Location'

SearchX = SearchXMin

SearchY = SearchYMin

'For for each location in the area,'

For Index = 1 To Area(VarArea).maxlocations

SearchX = SearchXMin

'And for each X...'

For Index2 = SearchXMin To SearchXMax

SearchX = SearchX + 1

'...Search each Y'

SearchY = SearchYMin

For Index3 = SearchYMin To SearchYMax

SearchY = SearchY + 1

If Area(VarArea).location(Index).x = SearchX And Area(VarArea).location(Index).y = SearchY Then

Area(VarArea).location(Index).Found = True

End If

If SearchY = SearchYMax Then

Exit For

End If

Next Index3

If SearchX = SearchXMax Then

Exit For

End If

Next Index2

Next Index

```

Is there anything in it that may be causing duplications? Otherwise, my bug must be elsewhere…

Edit;

Here is the output...

[](http://www.freemmorpgmaker.com/files/imagehost/#e7a6331cd76da71c54cd012b1da23185.png)

[Exception]

You know the distance check already, from what I've given you, so I'll provide this:

Graphing a circle on a 2D plane would look like this: x^2 + y^2 = radius^2.

Loop through the x - 3 to x + 3, and the same for y, and check if it's within the distance, and fits or is smaller than the radius. Should be simple. Good luck!

[azkanan]

Also, this is the code that lists the items to the listbox;

```

Index2 = 0

list_locations.Clear

For Index2 = 1 To Area(VarArea).maxlocations

If Area(VarArea).location(Index2).Found = True Then

If Area(VarArea).location(Index2).Traveled = False Then

If Index2 = Actor(0).locationlink Then

list_locations.AddItem "(!) ???" & " (" & Area(VarArea).location(Index2).Category & ")"

Else

list_locations.AddItem "???" & " (" & Area(VarArea).location(Index2).Category & ")"

End If

ElseIf Area(VarArea).location(Index2).Traveled = True Then

If Index2 = Actor(0).locationlink Then

list_locations.AddItem "(!)" & Area(VarArea).location(Index2).Name & " (" & Area(VarArea).location(Index2).Category & ")"

Else

list_locations.AddItem Area(VarArea).location(Index2).Name & " (" & Area(VarArea).location(Index2).Category & ")"

End If

End If

End If

Next Index2

```

[JeffSventora]

Maybe a bit much, but why not just implement greedy search or A Star?

[JohnPony]

> Maybe a bit much, but why not just implement greedy search or A Star?

I suggested this earlier.