Help with sorting algorithm

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
Joelrodiel
Prole
Posts: 27
Joined: Wed Apr 20, 2016 3:40 am

Help with sorting algorithm

Post by Joelrodiel » Mon Nov 12, 2018 9:29 pm

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:

Image

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

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

Re: Help with sorting algorithm

Post by Nelvin » 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

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

Re: Help with sorting algorithm

Post by Joelrodiel » Tue Nov 13, 2018 12:10 am

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

User avatar
pgimeno
Party member
Posts: 2177
Joined: Sun Oct 18, 2015 2:58 pm

Re: Help with sorting algorithm

Post by pgimeno » Tue Nov 13, 2018 12:30 am

Well, I'd start from the roof :nyu:

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] })

  -- Calculate a padding
  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
(5.17 KiB) Downloaded 30 times

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

Re: Help with sorting algorithm

Post by Joelrodiel » Tue Nov 13, 2018 6:06 am

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

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] })

  -- Calculate a padding
  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.

Post Reply

Who is online

Users browsing this forum: Google [Bot] and 13 guests