Forum

> > CS2D > Scripts > Check entity by using Bresen ham's line algorithm
Forums overviewCS2D overview Scripts overviewLog in to reply

English Check entity by using Bresen ham's line algorithm

2 replies
To the start Previous 1 Next To the start

old Check entity by using Bresen ham's line algorithm

_oops
User Off Offline

Quote
I'm trying to make blocking build portal if there is specified entity between player's position and player's cursor.

IMG:https://i.imgur.com/U3H3Anw.png

- Bluehole : Player's cursor
- Red : Player
- Green : Specified entity that blocks portal


I searched the solution in here and found Bresen ham's line algorithm and some people dropped solutions.
I tried to use those solutions but I ended up with wrong result.

look below picture

IMG:https://i.imgur.com/A2BMpvB.png


I was able to build portal with portal gun on purple squares but not on brown, also it was sightly slanted to the right.
Yes, I was able to build portals to the left.

This is the code that I used
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function distance(x1, y1, x2, y2)
    return math.floor(math.sqrt(math.pow(x1 - x2, 2) + math.pow(y1 - y2, 2)))
end

function freeline(x1, y1, x2, y2)
    for i=1, distance(x1, y1, x2, y2) do
        if entity(math.floor((x1 + i * math.cos(math.atan2(y2 - y1, x2 - x1))) / 32),math.floor((y1 + i * math.sin(math.atan2(y2 - y1, x2 - x1))) / 32), "name") == "killportal" then
            return true
        end
    end
    return false
end

addhook("attack","_attack")
function _attack(id)
	if ( freeline(player(id,"tilex"),player(id,"tiley"),player(id,"mousemapx"),player(id,"mousemapy")) then
	parse("killobject "..object(0,"table")[#object(0,"table")])
	end
end

I'm not good at math thingy.. so I'm search the solutions if the thing that I want to make requires the math.

I really appreicate if you give me hint to fix, not entire solutions. ( does not mean that I don't need solution. )

old Re: Check entity by using Bresen ham's line algorithm

DC
Admin Off Offline

Quote
You're in fact not using Bresenham at all. You're basically doing a raycast. That's also a legit solution but it's much slower. Especially when you don't cache important values and recalculate them in each iteration.

For instance your function
1
2
3
4
5
6
7
8
function freeline(x1, y1, x2, y2)
    for i=1, distance(x1, y1, x2, y2) do
        if entity(math.floor((x1 + i * math.cos(math.atan2(y2 - y1, x2 - x1))) / 32),math.floor((y1 + i * math.sin(math.atan2(y2 - y1, x2 - x1))) / 32), "name") == "killportal" then
            return true
        end
    end
    return false
end

Could be optimized a lot by just introducing a few variables (not tested):

1
2
3
4
5
6
7
8
9
10
11
12
function freeline(x1, y1, x2, y2)
    local angle = math.atan2(y2 - y1, x2 - x1)
    local deltaX = math.cos(angle)
    local deltaY = math.sin(angle)
    local dist = distance(x1, y1, x2, y2)
    for i=1, dist do
        if entity(math.floor((x1 + i * deltaX) / 32),math.floor((y1 + i * deltaY) / 32), "name") == "killportal" then
            return true
        end
    end
    return false
end

Bresenham would still be much faster as it wouldn't require to iterate each pixel of the "path" but only each tile. Currently you're checking each tile about 32 times (because it's 32x32 pixels, differs depending on the angle).

You could also simply improve your solution by using a bigger step size for the loop. Like only checking each 4th pixel - but this way you might miss tiles in some edge cases.

But like said before: Raycast should work as well. The problem I see is that you're using player(id, "tilex") which gives you the TILE position and player(id, "mousemap") which gives you the PIXEL position.
Using player(id, "x") instead (same for y of course) should help.

If you want to use Bresenham you can find a lot of implementations on the web. Luckily it's not a super complex algorithm
There's even a sample pseudo code implementation on Wikipedia.
https://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm
Should be easy to translate that to Lua.

old Re: Check entity by using Bresen ham's line algorithm

_oops
User Off Offline

Quote
@user DC:

So.. this is the result.

IMG:https://i.imgur.com/BsScLCx.gif


It was quietly random to make it happen. - like depends on the player's coordinates.

I was able to put the portal in front of entities but sometimes it blocks!

1
2
3
4
5
6
7
8
addhook("attack","_attack")
function _attack(id)
	-- if (player(id,"weapontype") == 88 ) then
		if ( freeline(player(id,"x"), player(id,"y"), player(id,"mousex"), player(id,"mousey")) ) then
		parse("killobject "..object(0,"table")[#object(0,"table")])
		end
	-- end
end

I used the code that you gave me, and I put some "print" functions in freeline for quick-dirty debug.

- and just found that why portals were not able to build on the slanted side not straightly.

silly analyzation here >


Guess, I'd better delay making this one? I actually have no clue how I can fix this.

---------------------------
I found an alternative way to solve this problem,
used two iterators to set start coordinate and destination.

IMG:https://i.imgur.com/EJlnI8a.gif


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
addhook("movetile","_movetile")
function _movetile(id,x,y)
	if ( entity(x,y,"name") == "portalkill" ) then
		for _,ob in pairs(object(0,"table")) do
			if ( object(ob,"player") == id and object(ob,"type") == 22 or object(ob,"type") == 23 ) then
			parse("killobject "..ob)
			end
		end
	end
end

addhook("attack","_attack")
function _attack(id)
local start_x, start_y, matchp = player(id,"tilex"), player(id,"tiley")
local dest_x, dest_y = math.floor(player(id,"mousemapx")/32), math.floor(player(id,"mousemapy")/32)
	if ( start_x > dest_x ) then 
	start_x, dest_x = dest_x, start_x
	end
	
	if ( start_y > dest_y ) then
	start_y, dest_y = dest_y, start_y
	end
	
		for x = start_x,dest_x do
			for y = start_y, dest_y do
				if ( entity(x,y,"name") == "portalkill" ) then				
				matchp = true
					if ( object(object(0,"table")[#object(0,"table")],"type") == 22 or object(object(0,"table")[#object(0,"table")],"type") == 23 ) then
					parse("killobject "..object(0,"table")[#object(0,"table")])
					break
					end
				end
			end
			if ( matchp ) then
			break
			end
		end
	-- end
end

addhook("attack2","_attack")

Messy code and might cause lag when lots of people are trying to build a portal.
But those lags can be reduced if I set some kind of "zone".
yay ! silly, and messy codes for someone who lookin for portal games.
edited 4×, last 01.09.18 03:47:19 pm
To the start Previous 1 Next To the start
Log in to reply Scripts overviewCS2D overviewForums overview