ID:1276803
 
I'm trying to create the fastest (most efficient) possible pixel projectile in DM

Here's what I've got so far:

#define WORLD_ICON_SIZE 64
#define WORLD_HALF_ICON_SIZE 32

var/tmp/projectiles = 0

atom/movable/proc/set_pos_px(px, py)
//this sets the tile (x, y) and the pixel(x, y) from absolute coordinates
src.x = px / WORLD_ICON_SIZE
src.y = py / WORLD_ICON_SIZE
src.pixel_x = px % WORLD_ICON_SIZE - WORLD_HALF_ICON_SIZE
src.pixel_y = py % WORLD_ICON_SIZE - WORLD_HALF_ICON_SIZE

proc/atan2(x, y)
//a quick atan2()
//I think lummox jr wrote this somewhere deep in the byond forum

if(!x && !y) return 0
return y >= 0 ? arccos(x / sqrt(x * x + y * y)) : -arccos(x / sqrt(x * x + y * y))

proc/get_angle(atom/a, atom/b)
//returns the angle between two atoms (in radians)
var/res = atan2(b.y - a.y, b.x - a.x)
res += 270//right hand conversion
while(res > 360) res -= 360
while(res <= 0) res += 360
return res

proc/get_dir_angle(atom/a, atom/b)
//converts an angle into a direction, for projectile facing
var/n = get_angle(a, b)
if(n >= 337.5 || n <= 22.5) return EAST
if(n >= 22.5 && n <= 67.5) return SOUTHEAST
if(n >= 67.5 && n <= 112.5) return SOUTH
if(n >= 112.5 && n <= 157.5) return SOUTHWEST
if(n >= 157.5 && n <= 202.5) return WEST
if(n >= 202.5 && n <= 247.5) return NORTHWEST
if(n >= 247.5 && n <= 292.5) return NORTH
if(n >= 292.5 && n < 337.5) return NORTHEAST

pixel_projectile
parent_type = /obj
animate_movement = NO_STEPS
var/tmp
angle = 0
px = 0 //the true pixel location of the projectile
py = 0
last_x = 0 //the last x/y coordinate of the tile we were in
last_y = 0
velocity = 10 //speed of the projectile
atom/owner

New()
..()
owner = usr
if(!owner) return
if(!owner:target) return
projectiles++

loc = owner.loc

if(owner.target == loc) del src

//set initial position
px = x * WORLD_ICON_SIZE + WORLD_HALF_ICON_SIZE
py = y * WORLD_ICON_SIZE + WORLD_HALF_ICON_SIZE

//calculate angle
angle = get_angle(src, owner.target)

//begin!
spawn update_loop()

Del()
projectiles--
..()

Cross(atom/movable/a)
//if something happens to cross this tile while we're sitting in it, which would happen after initially entering the tile
//we should check for collide!
if(a != src && a != owner) collide_with(a)
return ..()

proc/update_loop()
//update position
src.px = src.px + src.velocity * cos(src.angle)
src.py = src.py + src.velocity * -sin(src.angle)

//check if new position is valid
if(!check_bounds()) del src // ?

//update x, y, pixel_x, pixel_y to reflect new location
src.set_pos_px(src.px, src.py)

//did we enter a new tile?
if(last_x != x || last_y != y)
last_x = x
last_y = y

if(!loc) del src

//collide with everything in the tile
for(var/atom/a in loc.contents - src - owner)
collide_with(a)

//do it all over again, unless the world is slow, then wait a little longer
spawn(world.tick_lag * (world.cpu >= 10 ? world.cpu / 10 : 1)) update_loop()

proc/check_bounds()
//checks to see if a pixel is in bounds of the map
if(px < WORLD_ICON_SIZE || py < WORLD_ICON_SIZE || px >= (world.maxx + 1) * WORLD_ICON_SIZE || py >= (world.maxy + 1) * WORLD_ICON_SIZE)
return 0
return 1

proc/collide_with(atom/a)
//generic collide
if(a.type == src.type) return
//world << "[src] collides with [a]"
del src

pixel_projectile/test
icon = 'demo/gfx/mob.dmi'
icon_state = "bot"


Assumes:
-all atoms have a target variable which is equal to another atom at the time of firing. not necessary but I use that to calculate the angle at which to fire.
-assumes the owner is a mob, not a turf or an obj
-assumes the person who created the projectile is the owner
-this is a very basic projectile, there are many other cases where you might want the projectile to die (like if it runs into walls). those aren't handled here for simplicity sake of just making the fastest possible pixel projectile.

What I would really like to do is put delta_time in there somewhere so that as the loop updates get further apart from over-processing time... the projectiles actually move along at a frame independent speed.

Anyways, other than that, I don't see room for improvement. Anyone here be my guest and make a suggestion for improving the efficiency of the pixel_projectile!
Is there a reason you aren't using the default pixel movement in this? Why are you using px and py?
In response to Albro1
Albro1 wrote:
Is there a reason you aren't using the default pixel movement in this? Why are you using px and py?

It's for tile-based worlds.

You have way less control over pixel_based movement vs setting position from an absolute coordinate.

The px, and py are absolute coordinates, from which x, y, pixel_x, and pixel_y are formed. You could do away with those variables and set x, y, pixel_x, pixel_y every frame, but there would actually be more math / cpu powered involved there, so we use memory (px, py) to store the absolute location in the projectile, then form "where it will be on the map" each time we make an update.
In response to FIREking
There was no simple pixel movement library when I made shootah, but it was pretty fun.

Keep in mind that BYOND's map coordinate system starts with (1, 1) instead of (0, 0), which would cause bad things to happen when your absolute pixel coordinate is less than the tile size.

Also, to convert from angles (0 = EAST, increases counter-clockwise, the result from Lummox's atan2) and the other thing (0 = NORTH, increases clockwise), to use x = cos(angle) and y = sin(angle), you use 90 - angle, so x = cos(90 - angle) and y = sin(90 - angle). More recently, I stumbled upon the fact that you can simply switch them: x = sin(angle), y = cos(angle).
In response to Kaiochao
Kaiochao wrote:
There was no simple pixel movement library when I made shootah, but it was pretty fun.

Keep in mind that BYOND's map coordinate system starts with (1, 1) instead of (0, 0), which would cause bad things to happen when your absolute pixel coordinate is less than the tile size.

Also, to convert from angles (0 = EAST, increases counter-clockwise, the result from Lummox's atan2) and the other thing (0 = NORTH, increases clockwise), to use x = cos(angle) and y = sin(angle), you use 90 - angle, so x = cos(90 - angle) and y = sin(90 - angle). More recently, I stumbled upon the fact that you can simply switch them: x = sin(angle), y = cos(angle).

Nice tips. And thanks, I've already checked the edges of the map for proper behavior.
Meh, your point is mute because you're not sharing how you did it. The point of this post is to make it fast, as a community effort. Not to show that you can make it faster and then not share how you did it. No one will care about that.

Also, you disabled profiling so, there's no way to tell if your code is more efficient to mine because there's no performance report to compare to.

"Keep looking" isn't helpful so I'll wait for someone smarter to come along and share.
No src codez 4 u
Galactic Soldier wrote:
I can tell by your unnecessary calculations and loops that mine's more efficient than yours. Yeah, I know... I'm just saying that you didn't make the most efficient, and for you to keep trying.

I calculate the angle once at initialization, then I calculate the position once per frame. Thats it. What else am I calculating that is unnecessary?

Also, there is only one loop. You said loops.
Galactic Soldier wrote:
Yes, there are loops. Scrutinize your code carefully and believe me. You will improve if you succeed. :/
It's more of the mathematical fundamentals that you're working with, there's way more efficient ways. Well, really, I can see a lot of improvement that could be made in your code. Maybe I should just make a pixel projectile library.

Sure we can change how angle is calculated, which is much better done by someone who knows how to do so. I don't know how to do that, so I use the best thing I could find that accomplishes this task. Calculating the position can be doing with multiplication instead of division for a tiny increase, but not an increase that would matter.

The other bottlenecks are arbitrary and can be interpreted other ways (like how to handle colliding). The bare bones is the position calculation and the angle calculation, and I don't know any other faster ways to process them, which is why I made this post. The rest of the code is sketch work to see the math in action.
In response to FIREking
Indeed, no angle is necessary (unless you have a rotated icon, or something), and it is especially not necessary (if the angle is constant) to make a velocity vector every step of the way.

var dx = target.px() - px()
var dy = target.py() - py()
var r = sqrt(dx * dx + dy * dy)

var speed = constant
var vx = dx / r * speed
var vy = dy / r * speed

// <dx, dy> is a vector from the source to the target.
// divide it by r (the distance) to get a unit vector.
// scale that by 'speed' and you get a proper velocity vector

// unless your projectiles are heat-seeking, this only needs
// to be done once, upon creation, since velocity is constant.
In response to Kaiochao
He was dead on point.
Hmm, I definitely see how the other way is much better, but it actually isn't helping in the CPU department at all. They perform the same. Which is odd considering with the new method, all we're doing is adding to px, py of the projectile instead of using cos and sin.
In response to FIREking
In my experience, using a lookup sine/cosine table is much faster(and uses less memory) than using cos or sin. It'll require a lot more work, but the benefit should definitely be visible.
In response to Magnum2k
Magnum2k wrote:
In my experience, using a lookup sine/cosine table is much faster(and uses less memory) than using cos or sin. It'll require a lot more work, but the benefit should definitely be visible.

Sounds like a good point but now we're not even using cos and sin... so now its just finding a new bottleneck...
In response to Magnum2k
Looks like the bottle neck now is deciding what to collide with (currently we just build a list every single time we change tiles and try to collide with everything in the list). Not the best!
In response to FIREking
There's not much else to do. Back before native pixel movement, all we could do was check for atoms within a certain distance away.

Although, I wonder if bounds() can be used in non-pixel-movement. If so, you could then feed it the position of the projectile by using the absolute pixel position format. There's no avoiding generating a list to loop through, but this could make it more specific, and much shorter.
In response to Kaiochao
Kaiochao wrote:
There's not much else to do. Back before native pixel movement, all we could do was check for atoms within a certain distance away.

Although, I wonder if bounds() can be used in non-pixel-movement. If so, you could then feed it the position of the projectile by using the absolute pixel position format. There's no avoiding generating a list to loop through, but this could make it more specific, and much shorter.

obounds vs loc = not a huge difference if any that I could tell.

I'm currently able to get about 500 projectiles (released in the same tick) at once at around 35 CPU on my machine.
Got a huge increase by doing this:

pixel_projectile
proc/collide(atom/a)
del src

proc/can_collide(atom/a)
if(isturf(a))
if(a.density)
return 1
else
if(a != src && a != owner)
return 1
return 0
turf/var/list/collidables = null
turf/Entered(atom/a)
if(!collidables) collidables = list()
collidables += a

turf/Exited(atom/a)
if(!collidables) return
collidables -= a
if(!collidables.len) collidables = null

turf/proc/collide_here(pixel_projectile/p)
if(p.can_collide(src))
p.collide(src)
if(collidables)
for(var/atom/a in collidables)
if(p.can_collide(a))
p.collide(a)


Every time the projectile changes loc, you just call loc.collide_here(src)

Gained about 10% CPU doing this.
Ok so here is the current fastest functional non-homing single direction fixed velocity pixel_projectile:

#define WORLD_ICON_SIZE 64
#define WORLD_HALF_ICON_SIZE 32
#define WORLD_ICON_MULTIPLY 0.015625 //This is 1 / WORLD_ICON_SIZE
#define WORLD_MAX_PX 4160 //This is the size of your map in tiles + 1 times world_icon_size
#define WORLD_MAX_PY 4160 //This is the size of your map in tiles + 1 times world_icon_size

var/tmp/projectiles = 0

atom/movable/proc/set_pos_px(px, py)
//this sets the tile (x, y) and the pixel(x, y) from absolute coordinates
src.x = px * WORLD_ICON_MULTIPLY
src.y = py * WORLD_ICON_MULTIPLY
src.pixel_x = px % WORLD_ICON_SIZE - WORLD_HALF_ICON_SIZE
src.pixel_y = py % WORLD_ICON_SIZE - WORLD_HALF_ICON_SIZE

pixel_projectile
parent_type = /obj
animate_movement = NO_STEPS
var/tmp
angle = 0
px = 0 //the true pixel location of the projectile
py = 0
last_x = 0 //the last x/y coordinate of the tile we were in
last_y = 0
velocity = 12 //speed of the projectile
atom/owner

dx = 0 //delta px
dy = 0 //delta py
dr = 0 //root
vx = 0 //vector px (movement increment)
vy = 0 //vector py (movement increment)

New()
..()
projectiles++

//handle creation of the projectile... this is whatever
owner = usr
if(!owner:target)
del src

if(!owner:target.loc)
del src

loc = owner.loc

if(owner.target == loc) del src

//ok now the real important stuff, initial position and vector calculation

//set initial position
px = x * WORLD_ICON_SIZE + WORLD_HALF_ICON_SIZE
py = y * WORLD_ICON_SIZE + WORLD_HALF_ICON_SIZE

//delta x,y is absolute pixel x minus the starting absolute pixel x
dx = (owner.target.x * WORLD_ICON_SIZE) + WORLD_HALF_ICON_SIZE - px
dy = (owner.target.y * WORLD_ICON_SIZE) + WORLD_HALF_ICON_SIZE - py
//root
dr = sqrt(dx * dx + dy * dy)

//vector x (amount to move x,y each frame)
vx = dx / dr * velocity
vy = dy / dr * velocity

//set your direction here, however you want

//that's it

//begin!
spawn update_loop()

Del()
//garbage collector thing to save current tick cpu (null first, delete later)
if(loc)
loc = null
owner = null
for(var/atom/v in targeted)
v.target = null
target = null
targeted = null
return
projectiles--
..()

Cross(atom/movable/a)
//if something happens to cross this tile while we're sitting in it, which would happen after initially entering the tile
//we should check for collide!
if(can_collide(a)) collide(a)
return ..()

proc/update_loop()
//update position
px += vx
py += vy

if(!check_bounds()) del src

//update x, y, pixel_x, pixel_y to reflect new location
src.set_pos_px(src.px, src.py)

//did we enter a new tile?
if(last_x != x || last_y != y)
last_x = x
last_y = y

if(loc) loc:collide_here(src)

spawn(world.tick_lag) update_loop()

proc/check_bounds()
//checks to see if a pixel is in bounds of the map
if(px > WORLD_ICON_SIZE && py > WORLD_ICON_SIZE && px <= WORLD_MAX_PX && py <= WORLD_MAX_PY)
return 1
return 0

proc/collide(atom/a)
del src

proc/can_collide(atom/a)
if(isturf(a))
if(a.density)
return 1
else
if(a != src && a != owner)
return 1
return 0

pixel_projectile/test
icon = 'demo/gfx/mob.dmi'
icon_state = "missile"

//the collidables list allows us to avoid having to generate lists per tile update per projectile
//just make sure to remove your atom from this list at garbage collection!
turf/var/tmp/list/collidables = null
turf/Entered(atom/a)
if(!collidables) collidables = list()
collidables += a
..()

turf/Exited(atom/a)
if(!collidables) return
collidables -= a
if(!collidables.len) collidables = null
..()

turf/proc/collide_here(pixel_projectile/p)
if(p.can_collide(src))
p.collide(src)
if(collidables)
for(var/atom/a in collidables)
if(p.can_collide(a))
p.collide(a)
    proc/update_loop()
//update position
while(src)
px += vx
py += vy

if(!check_bounds()) del src

//update x, y, pixel_x, pixel_y to reflect new location
src.set_pos_px(src.px, src.py)

//did we enter a new tile?
if(last_x != x || last_y != y)
last_x = x
last_y = y

if(loc) loc:collide_here(src)

sleep(world.tick_lag)

Wouldn't this be better than recursively calling update_loop?
Page: 1 2