Tiled game: how find the closest fire?

Questions about the LÖVE API, installing LÖVE and other support related questions go here.
Forum rules
Before you make a thread asking for help, read this.
Post Reply
User avatar
togFox
Party member
Posts: 764
Joined: Sat Jan 30, 2021 9:46 am
Location: Brisbane, Oztralia

Tiled game: how find the closest fire?

Post by togFox »

So I have a tiled map and the player can ask an avatar to "fight closest fire".

Challenge: how to find the closest fire when there are two or more tiles containing a fire?

I have implemented jumper to path find but that's when the start and end point are known. I could use Dijkstra unweighted and weight graphs, but this is computational heavy and the two points are known.

Do I need to scan every tile?

Code: Select all

for each tile in map do
   if tile has fire then
      Use JUMPER to get distance   [does jumper do distance or steps?]
   end
end
Move avatar to the closest fire
Extinguish fire
Repeat
It would be quite trivial to code that in 10 lines or less but with multiple avatars executing that every 5 seconds or so on a map that may or may not be medium/big ...

Is there another way?
Current project:
https://togfox.itch.io/backyard-gridiron-manager
American football manager/sim game - build and manage a roster and win season after season
User avatar
darkfrei
Party member
Posts: 1168
Joined: Sat Feb 08, 2020 11:09 pm

Re: Tiled game: how find the closest fire?

Post by darkfrei »

For every tile in all tiles near the player check if this tile has a fire.
The list of fires can be sorted and used the nearest / one random of this several nearest fires.
This fire has a tiny priority by next search.
:awesome: in Lua we Löve
:awesome: Platformer Guide
:awesome: freebies
User avatar
togFox
Party member
Posts: 764
Joined: Sat Jan 30, 2021 9:46 am
Location: Brisbane, Oztralia

Re: Tiled game: how find the closest fire?

Post by togFox »

I'm going to try this:

check all tiles that are 1 distance away from the player (i.e. the 8 tiles next to the player)
If no fire then check tiles that are 2 distance away from the player (check 16 tiles)
If no fire then check tiles that are 3 distance away ... etc

So, in other words, check a box that is getting increasingly larger by 1 on each pass until a tile with fire is found. Then move to that fire, extinguish, then repeat. Makes sense?
Current project:
https://togfox.itch.io/backyard-gridiron-manager
American football manager/sim game - build and manage a roster and win season after season
User avatar
darkfrei
Party member
Posts: 1168
Joined: Sat Feb 08, 2020 11:09 pm

Re: Tiled game: how find the closest fire?

Post by darkfrei »

For some distance metrics - pretty well.

Here distance (x, y) to (x1, y1) and to (x1+1, y1) is same for (x1+1-x) <= (y1-y).
:awesome: in Lua we Löve
:awesome: Platformer Guide
:awesome: freebies
User avatar
togFox
Party member
Posts: 764
Joined: Sat Jan 30, 2021 9:46 am
Location: Brisbane, Oztralia

Re: Tiled game: how find the closest fire?

Post by togFox »

uh huh.

I haven't tested this yet - not near a love compiler:

Code: Select all

local row,col = GetClosestNeighbor(m, v, startx,starty)
	
local function GetClosestNeighbor(m, v, px,py)
-- m = map
-- v = value to look for
-- startx = the origin
-- starty = the origin
-- return 0,0 if nothing found

	local boundary = math.max(#m, #m[1])
	for i = 1 , boundary do	
		-- do the top row only
		row = (py - i)
		if row < 1 then row = 1 end
		for col = (px - i), (px + i) do
			if col < 1 then col = 1 end
			if col > #m[1] then col = #m[1] end
			if m[row][col] == v
				return row,col
			end
		end
		
		-- do the bottom row
		row = (py + i)
		if row > #m then row = #m end
		for col = (px - i), (px + i) do
			if col < 1 then col = 1 end
			if col > #m[1] then col = #m end
			if m[row][col] == v
				return row,col
			end
		end

		-- do the left column
		for row = (py - i), (py + i) do
			if row < 1 then row = 1 end
			if row > #m then row = #m end
			col = (px - i)
			if col < 1 then col = 1 end			
			if m[row][col] == v
				return row,col
			end
		end
		
		-- do the right column
		for row = (py - i), (py + i) do
			if row < 1 then row = 1 end
			if row > #m then row = #m end			
			col = (px + i)
			if col > #m[1] then col = #m end
			if m[row][col] == v
				return row,col
			end
		end	
	end
	
	return 0,0
end
Not elegant but, until I try to run it, I think it should work.
Current project:
https://togfox.itch.io/backyard-gridiron-manager
American football manager/sim game - build and manage a roster and win season after season
User avatar
darkfrei
Party member
Posts: 1168
Joined: Sat Feb 08, 2020 11:09 pm

Re: Tiled game: how find the closest fire?

Post by darkfrei »

Code and result:

code:

Code: Select all

local tabl = {}

function compare(a,b)
	return a.sd < b.sd
end

local square_radius = 10 -- sradius!

for x = -square_radius, square_radius do
	for y = -square_radius, square_radius do
		local sd = math.floor(x^2+y^2) -- squared distance
		table.insert (tabl, {x=x,y=y, sd = sd})
	end
end

table.sort(tabl, compare)

local tabl2 = {}
local ds = -1
local n = 0

for i, v in pairs (tabl) do
	--	print (i .. '	' .. v.x .. '	' .. v.y .. '	' .. v.sd)
	if ds < v.sd then
		ds = v.sd
		n = n + 1
		tabl2[n] = {}
	end
	table.insert (tabl2[n], v)
end

print ('tabl = {')
for i, v in pairs (tabl2) do
	local str = '{'
	for j,w in pairs (v) do
		str = str ..'{x='..w.x..', y='..w.y..'}, '
	end
	str = str:sub(1, -3)
	str = str..'},'
	print ('', ' -- elements: ' .. #v .. '; squared distance: '..v[1].sd)
	print ('', str)
end

print ('}')
result:

Code: Select all

tabl = {
	 -- elements: 1; squared distance: 0
	{{x=0, y=0}},
	 -- elements: 4; squared distance: 1
	{{x=1, y=0}, {x=0, y=-1}, {x=0, y=1}, {x=-1, y=0}},
	 -- elements: 4; squared distance: 2
	{{x=-1, y=-1}, {x=1, y=-1}, {x=1, y=1}, {x=-1, y=1}},
	 -- elements: 4; squared distance: 4
	{{x=0, y=2}, {x=2, y=0}, {x=-2, y=0}, {x=0, y=-2}},
	 -- elements: 8; squared distance: 5
	{{x=-2, y=-1}, {x=1, y=-2}, {x=2, y=1}, {x=2, y=-1}, {x=-1, y=-2}, {x=-1, y=2}, {x=-2, y=1}, {x=1, y=2}},
	 -- elements: 4; squared distance: 8
	{{x=2, y=2}, {x=2, y=-2}, {x=-2, y=-2}, {x=-2, y=2}},
	 -- elements: 4; squared distance: 9
	{{x=0, y=-3}, {x=-3, y=0}, {x=0, y=3}, {x=3, y=0}},
	 -- elements: 8; squared distance: 10
	{{x=-1, y=3}, {x=3, y=1}, {x=3, y=-1}, {x=-1, y=-3}, {x=1, y=3}, {x=-3, y=-1}, {x=-3, y=1}, {x=1, y=-3}},
	 -- elements: 8; squared distance: 13
	{{x=2, y=-3}, {x=-2, y=-3}, {x=-3, y=2}, {x=3, y=2}, {x=-2, y=3}, {x=-3, y=-2}, {x=3, y=-2}, {x=2, y=3}},
	 -- elements: 4; squared distance: 16
	{{x=0, y=-4}, {x=4, y=0}, {x=-4, y=0}, {x=0, y=4}},
	 -- elements: 8; squared distance: 17
	{{x=-1, y=-4}, {x=4, y=-1}, {x=-4, y=1}, {x=-4, y=-1}, {x=4, y=1}, {x=-1, y=4}, {x=1, y=-4}, {x=1, y=4}},
	 -- elements: 4; squared distance: 18
	{{x=-3, y=-3}, {x=3, y=3}, {x=3, y=-3}, {x=-3, y=3}},
	 -- elements: 8; squared distance: 20
	{{x=4, y=-2}, {x=-4, y=-2}, {x=2, y=-4}, {x=2, y=4}, {x=4, y=2}, {x=-4, y=2}, {x=-2, y=-4}, {x=-2, y=4}},
	 -- elements: 12; squared distance: 25
	{{x=5, y=0}, {x=-5, y=0}, {x=3, y=-4}, {x=-4, y=3}, {x=-3, y=4}, {x=0, y=-5}, {x=-4, y=-3}, {x=0, y=5}, {x=4, y=-3}, {x=3, y=4}, {x=4, y=3}, {x=-3, y=-4}},
	 -- elements: 8; squared distance: 26
	{{x=-1, y=5}, {x=5, y=1}, {x=1, y=5}, {x=-1, y=-5}, {x=-5, y=1}, {x=-5, y=-1}, {x=1, y=-5}, {x=5, y=-1}},
	 -- elements: 8; squared distance: 29
	{{x=2, y=5}, {x=-5, y=-2}, {x=-2, y=-5}, {x=5, y=2}, {x=5, y=-2}, {x=-2, y=5}, {x=-5, y=2}, {x=2, y=-5}},
	 -- elements: 4; squared distance: 32
	{{x=4, y=4}, {x=-4, y=4}, {x=-4, y=-4}, {x=4, y=-4}},
	 -- elements: 8; squared distance: 34
	{{x=-3, y=5}, {x=-5, y=3}, {x=-5, y=-3}, {x=5, y=3}, {x=3, y=5}, {x=-3, y=-5}, {x=5, y=-3}, {x=3, y=-5}},
	 -- elements: 4; squared distance: 36
	{{x=6, y=0}, {x=0, y=6}, {x=0, y=-6}, {x=-6, y=0}},
	 -- elements: 8; squared distance: 37
	{{x=1, y=-6}, {x=-1, y=6}, {x=-1, y=-6}, {x=1, y=6}, {x=6, y=-1}, {x=-6, y=1}, {x=-6, y=-1}, {x=6, y=1}},
	 -- elements: 8; squared distance: 40
	{{x=6, y=2}, {x=-6, y=2}, {x=-2, y=6}, {x=-6, y=-2}, {x=-2, y=-6}, {x=2, y=-6}, {x=2, y=6}, {x=6, y=-2}},
	 -- elements: 8; squared distance: 41
	{{x=-5, y=-4}, {x=-4, y=5}, {x=5, y=4}, {x=4, y=-5}, {x=-4, y=-5}, {x=5, y=-4}, {x=-5, y=4}, {x=4, y=5}},
	 -- elements: 8; squared distance: 45
	{{x=6, y=-3}, {x=6, y=3}, {x=3, y=6}, {x=3, y=-6}, {x=-6, y=3}, {x=-3, y=-6}, {x=-3, y=6}, {x=-6, y=-3}},
	 -- elements: 4; squared distance: 49
	{{x=0, y=-7}, {x=7, y=0}, {x=-7, y=0}, {x=0, y=7}},
	 -- elements: 12; squared distance: 50
	{{x=5, y=5}, {x=5, y=-5}, {x=-5, y=-5}, {x=7, y=1}, {x=-1, y=-7}, {x=1, y=7}, {x=1, y=-7}, {x=-1, y=7}, {x=-7, y=-1}, {x=-7, y=1}, {x=7, y=-1}, {x=-5, y=5}},
	 -- elements: 8; squared distance: 52
	{{x=4, y=6}, {x=6, y=4}, {x=4, y=-6}, {x=6, y=-4}, {x=-6, y=-4}, {x=-6, y=4}, {x=-4, y=6}, {x=-4, y=-6}},
	 -- elements: 8; squared distance: 53
	{{x=2, y=7}, {x=-7, y=-2}, {x=2, y=-7}, {x=-2, y=7}, {x=-7, y=2}, {x=7, y=-2}, {x=7, y=2}, {x=-2, y=-7}},
	 -- elements: 8; squared distance: 58
	{{x=3, y=7}, {x=-7, y=-3}, {x=-7, y=3}, {x=3, y=-7}, {x=-3, y=-7}, {x=7, y=-3}, {x=-3, y=7}, {x=7, y=3}},
	 -- elements: 8; squared distance: 61
	{{x=6, y=-5}, {x=6, y=5}, {x=5, y=6}, {x=-5, y=-6}, {x=-6, y=5}, {x=-5, y=6}, {x=5, y=-6}, {x=-6, y=-5}},
	 -- elements: 4; squared distance: 64
	{{x=0, y=-8}, {x=8, y=0}, {x=0, y=8}, {x=-8, y=0}},
	 -- elements: 16; squared distance: 65
	{{x=-4, y=7}, {x=1, y=8}, {x=7, y=-4}, {x=-1, y=8}, {x=7, y=4}, {x=-4, y=-7}, {x=1, y=-8}, {x=4, y=-7}, {x=8, y=1}, {x=4, y=7}, {x=-8, y=-1}, {x=-8, y=1}, {x=-7, y=-4}, {x=-1, y=-8}, {x=-7, y=4}, {x=8, y=-1}},
	 -- elements: 8; squared distance: 68
	{{x=8, y=2}, {x=2, y=-8}, {x=-8, y=2}, {x=-2, y=8}, {x=-2, y=-8}, {x=8, y=-2}, {x=-8, y=-2}, {x=2, y=8}},
	 -- elements: 4; squared distance: 72
	{{x=6, y=-6}, {x=6, y=6}, {x=-6, y=6}, {x=-6, y=-6}},
	 -- elements: 8; squared distance: 73
	{{x=3, y=8}, {x=8, y=3}, {x=-8, y=3}, {x=3, y=-8}, {x=8, y=-3}, {x=-3, y=8}, {x=-8, y=-3}, {x=-3, y=-8}},
	 -- elements: 8; squared distance: 74
	{{x=-5, y=-7}, {x=7, y=-5}, {x=-7, y=-5}, {x=7, y=5}, {x=5, y=7}, {x=-5, y=7}, {x=-7, y=5}, {x=5, y=-7}},
	 -- elements: 8; squared distance: 80
	{{x=4, y=8}, {x=4, y=-8}, {x=8, y=-4}, {x=-4, y=8}, {x=-4, y=-8}, {x=8, y=4}, {x=-8, y=-4}, {x=-8, y=4}},
	 -- elements: 4; squared distance: 81
	{{x=0, y=-9}, {x=-9, y=0}, {x=9, y=0}, {x=0, y=9}},
	 -- elements: 8; squared distance: 82
	{{x=9, y=1}, {x=-9, y=1}, {x=-1, y=9}, {x=1, y=-9}, {x=1, y=9}, {x=-1, y=-9}, {x=9, y=-1}, {x=-9, y=-1}},
	 -- elements: 16; squared distance: 85
	{{x=-7, y=6}, {x=-2, y=-9}, {x=6, y=-7}, {x=9, y=-2}, {x=-6, y=-7}, {x=-2, y=9}, {x=-9, y=2}, {x=-7, y=-6}, {x=2, y=9}, {x=7, y=6}, {x=2, y=-9}, {x=6, y=7}, {x=-9, y=-2}, {x=-6, y=7}, {x=9, y=2}, {x=7, y=-6}},
	 -- elements: 8; squared distance: 89
	{{x=8, y=-5}, {x=-5, y=-8}, {x=8, y=5}, {x=5, y=8}, {x=-5, y=8}, {x=-8, y=-5}, {x=5, y=-8}, {x=-8, y=5}},
	 -- elements: 8; squared distance: 90
	{{x=-3, y=-9}, {x=9, y=3}, {x=3, y=9}, {x=-9, y=-3}, {x=3, y=-9}, {x=-3, y=9}, {x=-9, y=3}, {x=9, y=-3}},
	 -- elements: 8; squared distance: 97
	{{x=9, y=-4}, {x=-9, y=4}, {x=4, y=9}, {x=-9, y=-4}, {x=-4, y=9}, {x=9, y=4}, {x=4, y=-9}, {x=-4, y=-9}},
	 -- elements: 4; squared distance: 98
	{{x=7, y=-7}, {x=-7, y=7}, {x=7, y=7}, {x=-7, y=-7}},
	 -- elements: 12; squared distance: 100
	{{x=6, y=-8}, {x=0, y=10}, {x=-8, y=-6}, {x=6, y=8}, {x=8, y=6}, {x=-8, y=6}, {x=0, y=-10}, {x=-6, y=-8}, {x=-10, y=0}, {x=8, y=-6}, {x=-6, y=8}, {x=10, y=0}},
	 -- elements: 8; squared distance: 101
	{{x=1, y=10}, {x=-10, y=1}, {x=1, y=-10}, {x=-10, y=-1}, {x=10, y=1}, {x=-1, y=10}, {x=10, y=-1}, {x=-1, y=-10}},
	 -- elements: 8; squared distance: 104
	{{x=10, y=-2}, {x=2, y=10}, {x=-10, y=-2}, {x=-2, y=-10}, {x=2, y=-10}, {x=-2, y=10}, {x=10, y=2}, {x=-10, y=2}},
	 -- elements: 8; squared distance: 106
	{{x=-9, y=5}, {x=9, y=5}, {x=9, y=-5}, {x=-9, y=-5}, {x=5, y=-9}, {x=5, y=9}, {x=-5, y=-9}, {x=-5, y=9}},
	 -- elements: 8; squared distance: 109
	{{x=10, y=3}, {x=10, y=-3}, {x=-10, y=3}, {x=-10, y=-3}, {x=-3, y=10}, {x=3, y=-10}, {x=-3, y=-10}, {x=3, y=10}},
	 -- elements: 8; squared distance: 113
	{{x=8, y=-7}, {x=8, y=7}, {x=7, y=8}, {x=7, y=-8}, {x=-7, y=-8}, {x=-7, y=8}, {x=-8, y=7}, {x=-8, y=-7}},
	 -- elements: 8; squared distance: 116
	{{x=-10, y=-4}, {x=-4, y=-10}, {x=-4, y=10}, {x=4, y=-10}, {x=10, y=4}, {x=4, y=10}, {x=-10, y=4}, {x=10, y=-4}},
	 -- elements: 8; squared distance: 117
	{{x=9, y=6}, {x=6, y=9}, {x=9, y=-6}, {x=6, y=-9}, {x=-9, y=-6}, {x=-6, y=-9}, {x=-9, y=6}, {x=-6, y=9}},
	 -- elements: 8; squared distance: 125
	{{x=-5, y=10}, {x=-5, y=-10}, {x=10, y=5}, {x=10, y=-5}, {x=-10, y=5}, {x=5, y=10}, {x=5, y=-10}, {x=-10, y=-5}},
	 -- elements: 4; squared distance: 128
	{{x=8, y=8}, {x=-8, y=8}, {x=8, y=-8}, {x=-8, y=-8}},
	 -- elements: 8; squared distance: 130
	{{x=7, y=9}, {x=-7, y=9}, {x=-9, y=-7}, {x=-9, y=7}, {x=9, y=-7}, {x=7, y=-9}, {x=-7, y=-9}, {x=9, y=7}},
	 -- elements: 8; squared distance: 136
	{{x=10, y=-6}, {x=-10, y=6}, {x=6, y=-10}, {x=10, y=6}, {x=6, y=10}, {x=-10, y=-6}, {x=-6, y=-10}, {x=-6, y=10}},
	 -- elements: 8; squared distance: 145
	{{x=9, y=-8}, {x=-9, y=-8}, {x=8, y=-9}, {x=-8, y=-9}, {x=8, y=9}, {x=9, y=8}, {x=-9, y=8}, {x=-8, y=9}},
	 -- elements: 8; squared distance: 149
	{{x=7, y=-10}, {x=-7, y=-10}, {x=10, y=-7}, {x=-7, y=10}, {x=-10, y=7}, {x=-10, y=-7}, {x=7, y=10}, {x=10, y=7}},
	 -- elements: 4; squared distance: 162
	{{x=-9, y=9}, {x=9, y=-9}, {x=9, y=9}, {x=-9, y=-9}},
	 -- elements: 8; squared distance: 164
	{{x=-10, y=8}, {x=-8, y=-10}, {x=-8, y=10}, {x=-10, y=-8}, {x=8, y=-10}, {x=10, y=8}, {x=10, y=-8}, {x=8, y=10}},
	 -- elements: 8; squared distance: 181
	{{x=10, y=-9}, {x=-10, y=-9}, {x=9, y=10}, {x=9, y=-10}, {x=-9, y=10}, {x=-9, y=-10}, {x=10, y=9}, {x=-10, y=9}},
	 -- elements: 4; squared distance: 200
	{{x=-10, y=-10}, {x=-10, y=10}, {x=10, y=-10}, {x=10, y=10}},
}
What is it: the list of sorted distances array of tiles, so you can process the list if no fires was found in this array of tiles.

First look at your tile: {{x=0, y=0}} -- elements: 1; squared distance: 0

if no fire here, skip to next line and seek for the fire in next fourth tiles:
{{x=1, y=0}, {x=0, y=-1}, {x=0, y=1}, {x=-1, y=0}} -- elements: 4; squared distance: 1

If no fire here, then next fourth tiles:
{{x=-1, y=-1}, {x=1, y=-1}, {x=1, y=1}, {x=-1, y=1}} -- elements: 4; squared distance: 2

etc. up to square-radius 10.

:oops: Update: actually, you must exclude all lines, that are larger than squared distance 100 for square-radius 10.
Attachments
euclidean-metric.lua
Euclidian metric for tiles; public domain
(724 Bytes) Downloaded 68 times
:awesome: in Lua we Löve
:awesome: Platformer Guide
:awesome: freebies
User avatar
darkfrei
Party member
Posts: 1168
Joined: Sat Feb 08, 2020 11:09 pm

Re: Tiled game: how find the closest fire?

Post by darkfrei »

Here the example how it works, there is the order priority, first nearest neighbours, than next nearest to center.
Attachments
Animation (42).gif
Animation (42).gif (241.75 KiB) Viewed 2992 times
neighbour-tiles-01.love
(1.29 KiB) Downloaded 66 times
:awesome: in Lua we Löve
:awesome: Platformer Guide
:awesome: freebies
User avatar
togFox
Party member
Posts: 764
Joined: Sat Jan 30, 2021 9:46 am
Location: Brisbane, Oztralia

Re: Tiled game: how find the closest fire?

Post by togFox »

I was thinking of doing four line scans (a box) adorns the player in ever increasing size and abusing when there is a hit, while being careful about scanning out of bounds.

I can see what you are doing with your approach. Thanks. :)
Current project:
https://togfox.itch.io/backyard-gridiron-manager
American football manager/sim game - build and manage a roster and win season after season
Post Reply

Who is online

Users browsing this forum: No registered users and 21 guests