Sign in to follow this  

Lineup for turn based games.

This topic is 822 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hey, I am creating a turn based combat system and I got it working but I'm not very proud of my algorithm. First, let me explain. My heroes have a speed stat, lower means better, and it could potentially range between 1000 to 1. When a hero with 3 speed can act 3 times before a hero with 10 speed can. I need a list of heroes to show the turn order and conveniently with my current algorithm I can pop the first on the list and add a new one. However I am looking for new heroes by increasing the time by 1 and keep looking for a new hero that should act. So I am traversing my hero loops countless times for nothing.

 

    private void updateLineUp()
    {
        while (lineUp.size() < 10)
        {
            //Check if tiebreaking pool has heroes in it
            if (tieBreakingPool.size() > 0)
            {
                //Check if there is only one hero in the tiebreaking pool to add it directly
                if (tieBreakingPool.size() == 1)
                {
                    Hero nextHero = tieBreakingPool.remove(0);
                    lineUp.add(nextHero);
                    System.out.println("[Time: " + futureTime + "] Added " + nextHero.getName() + " has " + nextHero.getSpeed() + " speed to the lineup.");
                }
                else
                {
                    //Pick random hero from the tieBreakingPool
                    Hero nextHero = tieBreakingPool.remove(random.nextInt(tieBreakingPool.size()));
                    lineUp.add(nextHero);
                    System.out.println("[Time: " + futureTime + "] Added " + nextHero.getName() + " has " + nextHero.getSpeed() + " speed to the lineup.");
                }
            }
            else { //search for new heroes to add

                //increment the future time for reference where the last hero is at.
                futureTime++;

                //find next heroes in line to add
                for (int i = 0; i < 5; i++) {
                    if (futureTime % playerHeroes[i].getSpeed() == 0) {
                        tieBreakingPool.add(playerHeroes[i]);
                    }
                    if (futureTime % opponentHeroes[i].getSpeed() == 0) {
                        tieBreakingPool.add(opponentHeroes[i]);
                    }
                }
            }
        }
    }

    private Hero getNextHero()
    {
        //remove first hero from list
        Hero hero = lineUp.remove(0);
        System.out.println("Popped " + hero.getName() + " from the lineup.");

        //update the line up
        updateLineUp();

        return hero;
    }

 

To get a list of the next 10 heroes takes only around 10ms so that is not bad at all since I only need a complete new list if the speed of the hero changes. But I'm not really looking for improving performance but rather coding style and cc on that.

Share this post


Link to post
Share on other sites

If your speeds are always integers, you could create buckets that represent each speed unit and then add each hero to all buckets that are multiples of their speed. Then you simply iterate over your buckets adding heroes to your lineup until you have enough.

 

eg: 3 heroes called H1 (has speed 2), H2 (has speed 3) and H3 (has speed 10)

 

Buckets:

1: (empty)

2: H1

3: H2

4: H1

5: (empty)

6: H1 and H2

7: (empty)

8: H1

9: H2

10: H1 and H3

..etc

 

Then, your line up is: H1, H2, H1, H1, H2, H1, H2, H1, H3

 

...It reminds me of the old "fizz buzz" programming question.

Share this post


Link to post
Share on other sites
I would recommend a priority queue. A priority queue stores it's elements in a binary tree, but still uses a queues Enqueue/Dequeue API. For example: Simulation begins at T=0. The priority queue requires at least two operations Enqueue, Dequeue Calling the enqueue operation inserts a node into a sorted binary tree with value T+speed Calling dequeue removes the left most node from the tree.

Share this post


Link to post
Share on other sites

This topic is 822 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this