Help with sorting algorithm

Questions about the LÖVE API, installing LÖVE and other support related questions go here.
Forum rules
Joelrodiel
Prole
Posts: 27
Joined: Wed Apr 20, 2016 3:40 am

Help with sorting algorithm

Hello, I've been working on a RPG lately, and I've hit a snag. When the fight sequence starts, I want the party members to appear in the screen, but I want it to sort their sprites as more members come. Kinda like a card algorithm, in the sense that you have one object, but when a new object appear, they get separated by some type of padding, and then when a third object comes around, the first object is at the right, the second at the left, and the third one in the middle, and so on? I have no idea what this can be called, but id love it if someone could help.

TL;DR:

This gif is what I wanna do with a table:

I have no idea how to approach it. Thank you in advance.

Nelvin
Party member
Posts: 118
Joined: Mon Sep 12, 2016 7:52 am
Location: Germany

Re: Help with sorting algorithm

local t = {}
table.insert( t, 1 + math.ceil(#t/2), 1 )
table.insert( t, 1 + math.ceil(#t/2), 2 )
table.insert( t, 1 + math.ceil(#t/2), 3 )
table.insert( t, 1 + math.ceil(#t/2), 4 )
table.insert( t, 1 + math.ceil(#t/2), 5 )

This creates a table with in the following order
1 - 3 - 5 - 4 - 2

Joelrodiel
Prole
Posts: 27
Joined: Wed Apr 20, 2016 3:40 am

Re: Help with sorting algorithm

Nelvin wrote:
Tue Nov 13, 2018 12:05 am
local t = {}
table.insert( t, 1 + math.ceil(#t/2), 1 )
table.insert( t, 1 + math.ceil(#t/2), 2 )
table.insert( t, 1 + math.ceil(#t/2), 3 )
table.insert( t, 1 + math.ceil(#t/2), 4 )
table.insert( t, 1 + math.ceil(#t/2), 5 )

This creates a table with in the following order
1 - 3 - 5 - 4 - 2
Hi Nelvin, sorry I don't think I was specific enough. I have the table and everything, all I need to know is how to draw the sprites in a way where they push each other to the sides corresponding on the amount in the table, like the gif shows

pgimeno
Party member
Posts: 2414
Joined: Sun Oct 18, 2015 2:58 pm

Re: Help with sorting algorithm

Well, I'd start from the roof

That is, start by determining the final position of each character, e.g. when you have two and you're going to make a 3rd one enter the scene, first determine the final positions of all three. This is easy if all of them are the same size, but it gets a bit complicated when the sizes may vary.

The initial and final Y positions are both constant, so let's not worry about it.

When there are going to be N characters, the total size from centre to centre of each character once they are in their positions is: size_c2c = (N - 1) * character_width + (N - 1) * padding. The leftmost character centre's X coordinate, relative to the centre of the screen, is minus half that number (because they will be distributed half that size in the negative direction and half that size in the positive direction, with respect to the centre). Let's call that left_base. So, left_base = -size_c2c / 2.

Now, for any character index 'j' from 1 to N, the final coordinate of that character will be: xpos[j] = left_base + (j - 1) * (character_width + padding).

With that, we have the positions necessary for N characters. Now all you have to do is tween all characters except the one that is coming in, from their previous position to their newly calculated position, and the one that is coming in, from the bottom of the screen at its final X position to the row's Y position.

But, wait, there's still something else to do. We have to insert the new character into its new position. That position is math.floor(N/2) + 1. Insert the element and you're ready for the next iteration.

For best effect, the padding could be calculated depending on N, like in your gif. A formula that might work is the inverse of N plus a minimum, for example math.floor(character_width/(N - 0.5) + 5) or something like that.

Putting everything together and in order, into Lua-like pseudocode:

Code: Select all

appearance_order = { player_to_appear_first, player_to_appear_second, player_to_appear_third }

function enter_next_character()
N = #characters_in_scene + 1

if N > #appearance_order then
appearance_finished() -- We're done, we can advance to the battle or whatever.
return
end

-- Start a timer that will call enter_next() after the time has passed
after(tween_time + pause_time, enter_next)

-- Find insert point, add new character
local insert_point = math.floor(N / 2) + 1
table_insert(characters_in_scene, insert_point, { character = appearance_order[N] })

local padding = math.floor(character_width / (N - 0.5) + 5)

-- Calculate size_c2c and left_base
local size_c2c = (N - 1) * character_width + (N - 1) * padding
local left_base = -math.floor(size_c2c / 2)

-- Prepare the next tween of each character and launch it
for j = 1, N do
local new_x = left_base + (j - 1) * (character_width + padding)
local current = characters_in_scene[j]
if j == insert_point then
-- Set the new character old_x the same as new_x, and old_y out of the screen
current.old_x = new_x
current.old_y = y_out_of_the_screen -- e.g. love.graphics.getHeight() + character_height / 2 + 0.5
else
-- Set the current character old coordinates to the previously used coordinates
current.old_x = current.new_x
current.old_y = current.new_y
end
-- Update the new coordinates with the new values
current.new_x = new_x
current.new_y = final_row_y  -- your final 'y' value, maybe the centre of the screen?

-- Tween current.x and current.y at the same time from old_* to new_* - see your tweening library's manual
tween(tween_time, current, {"x", "y"}, {current.old_x, current.old_y}, {current.new_x, current.new_y})
end
end

function love.draw()
for i = 1, #characters_in_scene do
local current = characters_in_scene[i]
-- Draw the characters appropriately centred
love.graphics.draw(current.character.image,
math.floor(current.x + 0.5) + screen_centre_x,
math.floor(current.y + 0.5),
0, 1, 1, -- angle, scale_x, scale_y
-- centre of the image
math.floor(current.character.image:getWidth() * 0.5),
math.floor(current.character.image:getHeight() * 0.5)
)
end
end

Edit: Proof of concept attached. Note it uses twimer.lua, which is my own timer/tween library that has not been publicly released, therefore don't use that library! Use some other one instead.
Attachments
insert-example.love

Joelrodiel
Prole
Posts: 27
Joined: Wed Apr 20, 2016 3:40 am

Re: Help with sorting algorithm

pgimeno wrote:
Tue Nov 13, 2018 12:30 am
Well, I'd start from the roof

That is, start by determining the final position of each character, e.g. when you have two and you're going to make a 3rd one enter the scene, first determine the final positions of all three. This is easy if all of them are the same size, but it gets a bit complicated when the sizes may vary.

The initial and final Y positions are both constant, so let's not worry about it.

When there are going to be N characters, the total size from centre to centre of each character once they are in their positions is: size_c2c = (N - 1) * character_width + (N - 1) * padding. The leftmost character centre's X coordinate, relative to the centre of the screen, is minus half that number (because they will be distributed half that size in the negative direction and half that size in the positive direction, with respect to the centre). Let's call that left_base. So, left_base = -size_c2c / 2.

Now, for any character index 'j' from 1 to N, the final coordinate of that character will be: xpos[j] = left_base + (j - 1) * (character_width + padding).

With that, we have the positions necessary for N characters. Now all you have to do is tween all characters except the one that is coming in, from their previous position to their newly calculated position, and the one that is coming in, from the bottom of the screen at its final X position to the row's Y position.

But, wait, there's still something else to do. We have to insert the new character into its new position. That position is math.floor(N/2) + 1. Insert the element and you're ready for the next iteration.

For best effect, the padding could be calculated depending on N, like in your gif. A formula that might work is the inverse of N plus a minimum, for example math.floor(character_width/(N - 0.5) + 5) or something like that.

Putting everything together and in order, into Lua-like pseudocode:

Code: Select all

appearance_order = { player_to_appear_first, player_to_appear_second, player_to_appear_third }

function enter_next_character()
N = #characters_in_scene + 1

if N > #appearance_order then
appearance_finished() -- We're done, we can advance to the battle or whatever.
return
end

-- Start a timer that will call enter_next() after the time has passed
after(tween_time + pause_time, enter_next)

-- Find insert point, add new character
local insert_point = math.floor(N / 2) + 1
table_insert(characters_in_scene, insert_point, { character = appearance_order[N] })

local padding = math.floor(character_width / (N - 0.5) + 5)

-- Calculate size_c2c and left_base
local size_c2c = (N - 1) * character_width + (N - 1) * padding
local left_base = -math.floor(size_c2c / 2)

-- Prepare the next tween of each character and launch it
for j = 1, N do
local new_x = left_base + (j - 1) * (character_width + padding)
local current = characters_in_scene[j]
if j == insert_point then
-- Set the new character old_x the same as new_x, and old_y out of the screen
current.old_x = new_x
current.old_y = y_out_of_the_screen -- e.g. love.graphics.getHeight() + character_height / 2 + 0.5
else
-- Set the current character old coordinates to the previously used coordinates
current.old_x = current.new_x
current.old_y = current.new_y
end
-- Update the new coordinates with the new values
current.new_x = new_x
current.new_y = final_row_y  -- your final 'y' value, maybe the centre of the screen?

-- Tween current.x and current.y at the same time from old_* to new_* - see your tweening library's manual
tween(tween_time, current, {"x", "y"}, {current.old_x, current.old_y}, {current.new_x, current.new_y})
end
end

function love.draw()
for i = 1, #characters_in_scene do
local current = characters_in_scene[i]
-- Draw the characters appropriately centred
love.graphics.draw(current.character.image,
math.floor(current.x + 0.5) + screen_centre_x,
math.floor(current.y + 0.5),
0, 1, 1, -- angle, scale_x, scale_y
-- centre of the image
math.floor(current.character.image:getWidth() * 0.5),
math.floor(current.character.image:getHeight() * 0.5)
)
end
end

Edit: Proof of concept attached. Note it uses twimer.lua, which is my own timer/tween library that has not been publicly released, therefore don't use that library! Use some other one instead.
Wow thank you so much for this response, this is just amazing. I will try to wrap my head around it haha, but again thank you so much. Also dont worry I wont copy and paste.

Who is online

Users browsing this forum: No registered users and 24 guests