#StackBounty: #unity #algorithm How to "place" object in a 3d world without overlapping them ?

Bounty: 150

I would like to place object in a 3d world “like minecraft player can do”.

What I’m trying to do is to allow the user to place objects, without overlapping them (like in minecraft you can do).

So if the player try to place an object partially over another, my game automatically “move and place” the object in the allowed position.

What can be the right approach ?


Get this bounty!!!

#StackBounty: #java #performance #algorithm #guava Generating a string in a particular format by reading data from a map

Bounty: 50

I have a processToTaskIdHolder Map which contains processId as the key and taskId as the value. Now I am iterating this map and at the end I am making a String in particular format.

For example:-

  • Let’s say I have 123 as the key and 009 is the value in the processToTaskIdHolder map.
  • Now I will make a “activityKey” using 123 and then get data basis on this key.
  • Now I will iterate all the categories for that activityKey and check whether those categoryId are already present in processToTaskIdHolder keyset or not. If they are present, then I will extract taskId for that categoryId from the map and also extract score for that categoryId and store it in an Info class.
  • Same category can be present with different score for different processId.

Now I need to repeat above steps for each activity I have in activities list.

So my formatted string will be like this:-

A,B,C:Score1,D:Score2
P,Q,R:Score1,S:Score2
  • Where A is the categoryId for the processId C and D, and Score1 is the score for categoryId A for processId C. Score2 is the score for categoryId A but for processId D. We have different scores for same categories for two different processes. It means, categoryId A was present in both processId C and D so I need to get the score for both the cases and make a string like that. And B is the taskId for categoryId A which will be present in the map.
  • Where P is the categoryId for the processId R and S, and Score1 is the score for categoryId P for processId R. Score2 is the score for categoryId P but for processId S. We have different scores for same categories for two different processes. It means, categoryId P was present in both processId R and S so I need to get the score for both the cases and make a string like that. And Q is the taskId for categoryId P which will be present in the map.

I have this code which does the job but I think it’s not the right and efficient way to achieve above formatted string. I believe it can be done in a much better way.

  private static final List<String> activities = Arrays.asList("tree", "gold", "print", "catch");

  public static void reverseLookup(final String clientId, final Map<String, String> processToTaskIdHolder) {
    Multimap<String, Info> reverseLookup = LinkedListMultimap.create();
    for (String activity : activities) {
      for (Entry<String, String> entry : processToTaskIdHolder.entrySet()) {
        String activityKey = "abc_" + activity + "_" + clientId + "_" + entry.getKey();
        Optional<Datum> datum = getData(activityKey);
        if (!datum.isPresent()) {
          continue;
        }
        List<Categories> categories = datum.get().getCategories();
        for (Categories category : categories) {
          String categoryId = String.valueOf(category.getLeafCategId());
          if (processToTaskIdHolder.containsKey(categoryId)) {
            Info info = new Info(entry.getKey(), String.valueOf(category.getScore()));
            reverseLookup.put(categoryId + ":" + processToTaskIdHolder.get(categoryId), info);
          }
        }
      }
      String formattedString = generateString(reverseLookup);
      System.out.println(formattedString);
    }
  }

  private static String generateString(final Multimap<String, Info> reverseLookup) {
    StringBuilder sb = new StringBuilder();
    for (Entry<String, Collection<Info>> entry : reverseLookup.asMap().entrySet()) {
      sb.append(entry.getKey().split(":")[0]).append(",").append(entry.getKey().split(":")[1])
          .append(",");
      String sep = "";
      for (Info info : entry.getValue()) {
        sb.append(sep).append(info.getLeafCategoryId()).append(":").append(info.getScore());
        sep = ",";
      }
      sb.append(System.getProperty("line.separator"));
    }
    return sb.toString();
  }

In the reverseLookup map, I have a key in this format – “a:b”, so I’m not sure instead of making a key like that. Maybe it can be done in some other better way?

Note: I am working with Java 7. Categories and Info class is a simple immutable class with basic toString implementations.


Get this bounty!!!

#StackBounty: #php #python #c++ #algorithm #sorting Table cells / 2d array sorting algorithm

Bounty: 50

Is there an algorithm that could help sort the left table (which is an abstraction for multidimensional array of scalars or objects) down below so the result would be as in the right one, given that there maybe a limited amount of available depth in the right table (e.g. max of 30 rows)?

enter image description here

And slightly more complex version of the problem (first key in a cell is having precedence over another):

enter image description here

EDIT: And another level of complexity (merge rows/levels if it’s safe to do so to prevent redundancy):

enter image description here


Get this bounty!!!

#StackBounty: #python #performance #algorithm #multiprocessing Creating a graph representing all combinations of 4-bit binary strings

Bounty: 100

I have an algorithm that creates a graph that has all representations of 4-bit binary strings encoded in the form of the shortest graph paths, where an even number in the path means 0, while an odd number means 1:

from itertools import permutations, product
import networkx as nx
import matplotlib.pyplot as plt
import progressbar
import itertools

g = nx.Graph()

dodane_pary=[]   

def groups(sources, template):
    func = permutations
    keys = sources.keys()
    combos = [func(sources[k], template.count(k)) for k in keys]
    for t in product(*combos):
        d = {k: iter(n) for k, n in zip(keys, t)}
        yield [next(d[k]) for k in template]                                      

bar = progressbar.ProgressBar(maxval=len(list(itertools.product(tuple(range(2)), repeat=4)))).start()
count=1
dobre2=[]
# I create 4-bit binary strings
for y,i in enumerate(itertools.product(tuple(range(2)), repeat=4)): 
    # I do not include one of the pairs of binary strings that have a mirror image
    if tuple(reversed(i)) >= tuple(i):
       # I create representations of binary strings, where 0 is 'v0' and 1 is 'v1'. For example, the '001' combination is now 'v0v0v1'
       a = ['v{}'.format(x%2) for x in i] 

       if len(dodane_pary)!=count+1:
           # I add an even number if it was not or an odd number if it was not in the 'dobre2' list
           for p in range(2):
               if len([i for i in dobre2 if i%2 == p ])==0:
                   dobre2.insert(p,p)

           h=0          
           while len(dodane_pary)<count:   

            if h!=0:   
               # extends the list 'dobre2' by subsequent even and odd numbers if the step 'h = 0' did not give the desired effects
               for q in range(2):   
                   g.add_node([i for i in dobre2 if i%2 == q][-1] + 2)
                   dobre2.append([i for i in dobre2 if i%2 == q][-1] + 2)

            sources={}
            for x in range(2):
                sources["v{0}".format(x)] = [i for i in dobre2 if i%2 == x]
            # for each representation in the form 'v0v0v1' for example, I examine all combinations of strings where 'v0' is an even number 'a' v1 'is an odd number, choosing values from the' dobre2 'list and checking the following conditions.
            for aaa_binary in groups(sources, a):

                if len(dodane_pary)!=count:
                    # adding new nodes and edges if they did not exist
                    g.add_nodes_from (aaa_binary)
                    t1 = (aaa_binary[0],aaa_binary[1])
                    t2 = (aaa_binary[1],aaa_binary[2])
                    t3 = (aaa_binary[2],aaa_binary[3])

                    added_now = []                      
                    for edge in (t1,t2,t3):
                        if not g.has_edge(*edge):
                           g.add_edge(*edge)
                           added_now.append(edge)

                    dodane_pary.append(aaa_binary)  
                    # checking the condition whether the shortest path condition on the existing graph is met after the added edges. if not, newly removed edges remove.
                    for j in range(len(dodane_pary)):
                        if nx.shortest_path(g, aaa_binary[0], aaa_binary[3])!=aaa_binary or nx.shortest_path(g, dodane_pary[j][0], dodane_pary[j][3])!=dodane_pary[j]:
                           for edge in added_now:
                               g.remove_edge(*edge)
                           dodane_pary.remove(aaa_binary)
                           break
                if len(dodane_pary)==count: 
                   break 
            h=h+1

       count +=1
       bar.update(y)

g.remove_nodes_from(nx.isolates(g))

pos=nx.circular_layout(g)
plt.figure(3,figsize=(8,8))
nx.draw_networkx_edges(g,pos)
nx.draw(g,pos)   
nx.draw_networkx_labels(g,pos)

print (dodane_pary)

plt.show()

Output paths representing 4-bit binary strings from dodane_pary:

[[0, 2, 4, 6], [0, 2, 4, 1], [0, 2, 3, 8], [0, 2, 3, 5], [2, 3, 8, 7], [6, 1, 3, 8], [2, 3, 5, 9], [11, 0, 2, 3], [11, 4, 1, 5], [7, 1, 5, 9]]

So these are representations of 4-bit binary strings:

[0000, 0001, 0010, 0011, 0101, 0110, 0111, 1001, 1011, 1111] 

Of course, as you can see, there are no reflections of the mirrored strings, because there is no such need in an undirected graph.

Graph:

enter image description here

The time the code works is the biggest problem. Because in this quite simple example at the end of the algorithm’s operation, the dobre2 list has 12 values:[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11], from which the tested there are all four-element sub-lists. However, for example, I would like to build a graph with all representations of 8-bit strings. It’s easy to imagine what size the dobre2 list will grow to at some stage.

And unfortunately I do not see any other way to check step-by-step, because I have not found any mathematical theory matching my problem. For example, the Hamilton cube is built a little differently.

Can multiprocessing be used in the code constructed in this way? I ask because I’ve tried everything but to no avail.

While trying to speed up the operation of the code, I also tried to reject the combinations written to an additional list, but unfortunately such a list quickly grows to very large sizes and placing a condition checking whether a given combination exists on the list, which further extends the algorithm’s working time.

Or maybe you can somehow optimize the code? I will be grateful for every clue.

Ps. I’ve tried everything to implement multiprocessing. Help me please 🙂


Get this bounty!!!

#StackBounty: #unity #algorithm #camera How to calculate Camera "correct" position and distance to Frame all my Scene?

Bounty: 100

Consider I have N dynamic points on my Scene, I would like to “frame” all them, with my Camera.
enter image description here

How can i calculate (at runtime) Vector3 Position to correctly frame all my scene ?

This is my idea:

  1. Calculate Avarage for all my points

  2. Move my Camera “up” to correctly “frame” all my points (i don’t know how)

  3. Use Unity LookAt(myAvaragePoint)

Thanks


Get this bounty!!!

#StackBounty: #algorithm #geometry #subdivision Visualizing the Lane-Riesenfeld Algorithm

Bounty: 50

Ok so, I keep reading papers about this and non of them have pictures. The lane Riesenfeld algorithm provides a way to subdivide set of points with B-spline conversion.

The quesiton is simple HOW? If you can give me a set of pictures with the explanation that’s be the best explanation, more than the math.

The first step (i.e duplication of the original vertices) seems clear enough, but I do not fully understand how the mid point averaging works.

Currently my very, very poor understanding is producing this:

Starting with the following 4 points

enter image description here

We duplicate each point (denoted by the grey area)

enter image description here

We take all odd points in our new set, and move them to the middle of the line connecting 2 consecutive points:

enter image description here

What do I do now? From here on I am just completely lost


Get this bounty!!!

#StackBounty: #java #algorithm #game #collision Handling collision on a turn-based 2D game

Bounty: 100

I have implemented a collision check algorithm that I have created for my game, and the algorithm uses recursion.

Now it all works fine, and I thought to myself, what if there was a way to solve this algorithm, without using recursion, and more something with promise callbacks, or something, but unfortunately after researching, I could not find any way that I can think of at this time, so I thought I should ask there.

Now by turn-based I mean that the game is basically a big board of rectangles where each rectangle is a tile position, and there are ships, each ship can be on a tile unless its a rock, or another ship on there.

Now the collision is handled server-sided, so the coordinates are always integers, so it’s not some graphical collision check, don’t get me wrong.

There’s an Example of collision, you can see that the ship selected the moves Right, Left, Right, and the left move collided, because the other ship does not move at that turn of the move.

So how does my algorithm work

    // Loop through all turns
    for (int turn = 0; turn < 4; turn++) {
        // Loop through phases in the turn (split turn into phases, e.g turn left is 2 phases, turn forward is one phase).
        // So if stopped in phase 1, and its a turn left, it will basically stay in same position, if in phase 2, it will only
        // move one step instead of 2 full steps.
        for (int phase = 0; phase < 2; phase++) {

             // Go through all players and check if their move causes a collision
             for (Player p : players) {

                 // If a player is already collided in this step, we don't want him to move
                 // anywhere, so we skip this iteration
                 if (p.getCollisionStorage().isCollided(turn)) {
                     continue;
                 }

                 // Checks collision for the player, according to his current step #phase index and turn
                 collision.checkCollision(p, turn, phase, true);
           }
        }
     }

So basically checkCollision(Player p, int turn, int phase, boolean setPos) is where the collision is handled, and is a big method. This method basically goes through the collision rules and saves into players’ collision storage if it collided or not.

But here comes the recursion part: When a tile is already claimed, in the method, we check if the claimed player has a move placed on that turn, if yes, we will run the checkCollision method on that player that claimed it, if the player collided during his move, the method will return true, and then we know that this claimed player did not move, so the player we check for will collide with him. And now imagine a line of ships, and ship A wants to move forward, so we check ship B, ship B checks ship C and on and on and makes sure that every checkCollision returned false, so ship A can move and rest can move as-well.

Now I am curious, if there is a better way on implementing this besides using a recursion?

/**
 * Checks if a player has a collision according to his move, in the given turn and move-phase
 * @param p             The player to check
 * @param turn          The turn
 * @param phase         The move-phase step
 * @param setPosition   If to set the next position or not on non-collided result
 * @return  <code>TRUE</code> If the player was collided, <code>FALSE</code> if not.
 */
public boolean checkCollision(Player p, int turn, int phase, boolean setPosition) {
    // The current selected move of the player
    MoveType move =  p.getMoves().getMove(turn);

    // If this player was bumped, and a move was not selected, we want to process the bump animation
    // But we have to check if the position to be bumped is available to be claimed
    if (move == MoveType.NONE && p.getCollisionStorage().isBumped()) {
        Position pos = p.getCollisionStorage().getBumpAnimation().getPositionForAnimation(p);
        Player claimed = players.getPlayerByPosition(pos.getX(), pos.getY());
        // Claiming checking for the new position for bump
        return claimed != null && (claimed.getMoves().getMove(turn) == MoveType.NONE || checkCollision(claimed, turn, phase, false));
    }

    // Use the current position as default, imply we have already set it
    Position position = p;

    // If not set by default.txt on previous loops, gets the next position on the map for the given phase on the given move
    if (!p.getCollisionStorage().isPositionChanged()) {
        position = move.getNextPositionWithPhase(p, p.getFace(), phase);
    }
    // If the player has moved since his last position
    if (!position.equals(p)) {
        // Check for bounds collision with the border
        if (checkBoundCollision(p, turn, phase) || checkRockCollision(p, turn, phase)) {
            return true;
        }
        // Check if the next position is claimed by another player, null result if not
        Player claimed = players.getPlayerByPosition(position.getX(), position.getY());

        // If the result is not null, the position is claimed
        if (claimed != null) {
            Position claimedNextPos = claimed;
            if (!claimed.getCollisionStorage().isPositionChanged()) {
                claimedNextPos = claimed.getMoves().getMove(turn).getNextPositionWithPhase(claimed, claimed.getFace(), phase);
            }

            // Check if the claimed position doesn't move away
            if (claimed.getMoves().getMove(turn) == MoveType.NONE || claimedNextPos.equals(claimed)) {
                if (move != MoveType.FORWARD || claimed.getVessel().getSize() >= p.getVessel().getSize()) {
                    collide(p, claimed, turn, phase);
                }

                if (move == MoveType.FORWARD && canBumpPlayer(p, claimed, turn, phase)) {
                    bumpPlayer(claimed, p, turn, phase);
                    p.set(position);
                    p.getCollisionStorage().setPositionChanged(true);
                }

                claimed.getVessel().appendDamage(p.getVessel().getRamDamage());

                return true;
            }
            else if (claimedNextPos.equals(p)) { // If they switched positions (e.g nose to nose, F, F move)
                collide(p, claimed, turn, phase);
                collide(claimed, p, turn, phase);
                return true;
            }
            else {
                // Make sure that the claimed position moves away successfully
                if (!checkCollision(claimed, turn, phase, false)) {
                    if (setPosition) {
                        // Moved successfully, claim position
                        p.set(position);
                        p.getCollisionStorage().setPositionChanged(true);
                    }
                }
                else {
                    // did not move successfully, collide
                    collide(p, claimed, turn, phase);
                    collide(claimed, p, turn, phase);
                    return true;
                }
            }
        } else {
            // List of players that collided with this player, while performing this move, in this phase
            List<Player> collisions = getPlayersTryingToClaim(p, position, turn, phase);

            if (collisions.size() > 0) { // Collision has happened
                collisions.add(p);

                Player largest = getLargestSize(collisions);

                if (countPlayersForSize(collisions, largest.getVessel().getSize()) > 1) {
                    // Stop players from movement
                    for (Player pl : collisions) {
                        pl.getCollisionStorage().setCollided(turn, phase);
                        collide(pl, pl, turn, phase);
                    }
                }
                else {
                    for (Player pl : collisions) {
                        if (pl == largest) {
                            continue;
                        }
                        pl.getCollisionStorage().setCollided(turn, phase);
                        collide(pl, largest, turn, phase);
                    }
                    if (!largest.getCollisionStorage().isPositionChanged()) {
                        largest.set(position);
                        largest.getCollisionStorage().setPositionChanged(true);
                    }
                }
                return true;
            } else {
                if (setPosition) {
                    p.set(position);
                    p.getCollisionStorage().setPositionChanged(true);
                }
            }
        }
    }

    return false;
}


Get this bounty!!!

#StackBounty: #java #algorithm #recursion #comparative-review #backtracking Two approaches to print all permutations – returning versus…

Bounty: 50

I have noticed many of the backtracking problems have two ways of solving.

One is to return “whatever’s the required list”, vs passing-through the “result” to every call and appending to it. What is the downside of returning (is it less memory/time efficient)? Example – To print all possible permutations, what makes this solution inefficient vs the second one.

public List<List<Integer>> perm(int[] nums){
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    if(nums.length == 0){
        result.add(new ArrayList<Integer>());
        return result;        
    }
    for(int i= 0;i<nums.length;i++){
        int first = nums[i];
        int[] remnums = new int[nums.length-1];
        int j = 0;
        for(int cur : nums){
            if(cur != first){
                remnums[j] = cur;j++;
            }
        }
        List<List<Integer>> tmp = perm(remnums);

        for(List<Integer> t : tmp){
            t.add(0,first);

        }
        result.addAll(tmp);
    }
    return result;
}

2nd approach —

public List<List<Integer>> permute(int[] nums) {
   List<List<Integer>> list = new ArrayList<>();
   // Arrays.sort(nums); // not necessary
   backtrack(list, new ArrayList<>(), nums);
   return list;
}

private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums){
   if(tempList.size() == nums.length){
      list.add(new ArrayList<>(tempList));
   } else{
      for(int i = 0; i < nums.length; i++){ 
         if(tempList.contains(nums[i])) continue; // element already exists, skip
         tempList.add(nums[i]);
         backtrack(list, tempList, nums);
         tempList.remove(tempList.size() - 1);
      }
   }
} 


Get this bounty!!!

#StackBounty: #java #performance #algorithm #swing #computational-geometry Java algorithm to declutter rectangles

Bounty: 100

I’ve been working on an algorithm to declutter rectangles. It seems to work fine when I have less than 1,000 rectangles, but becomes much slower when there are 10,000, which I believe to be because the algorithm is inefficient with large datasets. I’m looking to find ways to optimize to perform better with more rectangles.

The code I have is based on this algorithm (which is based on this SO answer from another similar question: https://stackoverflow.com/a/3266158/33863):


Find the center C of the bounding box of your rectangles.

For each rectangle R that overlaps another:

  • Define a movement vector v.
  • Find all the rectangles R’ that overlap R.
  • Add a vector to v proportional to the vector between the center of R and R’.
  • Add a vector to v proportional to the vector between C and the center of R.
  • Move R by v.
  • Repeat until nothing overlaps.

This incrementally moves the rectangles away from each other and the center of all the rectangles. This will terminate because the component of v from step 4 will eventually spread them out enough all by itself.


Here is the code I’m working with:

public class Rectangles extends JPanel {

    // Create sample rectangles laid out in frame
    List<Rectangle2D> rectangles = new ArrayList<Rectangle2D>();
    {
        // x,y,w,h
        // random rectangles
        rectangles.add(new Rectangle2D.Float(300, 50, 50, 50));
        rectangles.add(new Rectangle2D.Float(300, 50, 20, 50));
        rectangles.add(new Rectangle2D.Float(100, 100, 100, 50));
        rectangles.add(new Rectangle2D.Float(120, 200, 50, 50));
        rectangles.add(new Rectangle2D.Float(150, 130, 100, 100));
        rectangles.add(new Rectangle2D.Float(0, 100, 100, 50));
        rectangles.add(new Rectangle2D.Float(690, 229, 388, 114));
        rectangles.add(new Rectangle2D.Float(347, 341, 347, 425));
        rectangles.add(new Rectangle2D.Float(107, 515, 179, 158));
        rectangles.add(new Rectangle2D.Float(55, 487, 174, 153));
        rectangles.add(new Rectangle2D.Float(458, 553, 125, 128));
        rectangles.add(new Rectangle2D.Float(109, 566, 125, 128));
        rectangles.add(new Rectangle2D.Float(138, 166, 125, 128));


        int numRowsAndColumns = 20;
//      int numRowsAndColumns = 50;
//      int numRowsAndColumns = 100;
//      Add more rectangles
        for (int i = 0; i < numRowsAndColumns; i++) {
            for (int j = 0; j < numRowsAndColumns; j++) {
                rectangles.add(new Rectangle2D.Float(i * 20, j * 10, 25, 20));
            }
        }


        System.out.println("Num Rectangles " + rectangles.size());
    }

    //The list of rectangles that are drawn on the screen
    List<Rectangle2D> rectanglesToDraw;

    //reset the view back to the unaffected rectangles
    protected void reset() {
        rectanglesToDraw = rectangles;

        this.repaint();
    }

    //Given a rectangle, find the rectangles from the rectList that intersect with it
    private List<Rectangle2D> findIntersections(Rectangle2D rect, List<Rectangle2D> rectList) {

        ArrayList<Rectangle2D> intersections = new ArrayList<Rectangle2D>();

        for (Rectangle2D intersectingRect : rectList) {
            if (!rect.equals(intersectingRect) && intersectingRect.intersects(rect)) {
                intersections.add(intersectingRect);
            }
        }

        return intersections;
    }

    //main algorithm that attempts to declutter the rectangles.    
    protected void fix() {
        rectanglesToDraw = new ArrayList<Rectangle2D>();

        //make copies to keep original list unaffected
        for (Rectangle2D rect : rectangles) {
            Rectangle2D copyRect = new Rectangle2D.Double();
            copyRect.setRect(rect);
            rectanglesToDraw.add(copyRect);
        }

        // Find the center C of the bounding box of your rectangles.
        Rectangle2D surroundRect = surroundingRect(rectanglesToDraw);
        Point center = new Point((int) surroundRect.getCenterX(), (int) surroundRect.getCenterY());

        int numIterations = 0;

        int movementFactor = 10; //ideally would be 1

        boolean hasIntersections = true;

        //keep going until there are no intersections present    
        while (hasIntersections) {

            //initialize to false within the loop.  
            hasIntersections = false;

            for (Rectangle2D rect : rectanglesToDraw) {

                // Find all the rectangles R' that overlap R.
                List<Rectangle2D> intersectingRects = findIntersections(rect, rectanglesToDraw);

                if (intersectingRects.size() > 0) {

                    // Define a movement vector v.
                    Point movementVector = new Point(0, 0);

                    Point centerR = new Point((int) rect.getCenterX(), (int) rect.getCenterY());

                    // For each rectangle R that overlaps another.
                    for (Rectangle2D rPrime : intersectingRects) {
                        Point centerRPrime = new Point((int) rPrime.getCenterX(), (int) rPrime.getCenterY());

                        int xTrans = (int) (centerR.getX() - centerRPrime.getX());
                        int yTrans = (int) (centerR.getY() - centerRPrime.getY());

                        // Add a vector to v proportional to the vector between the center of R and R'.
                        movementVector.translate(xTrans < 0 ? -movementFactor : movementFactor,
                                yTrans < 0 ? -movementFactor : movementFactor);

                    }

                    int xTrans = (int) (centerR.getX() - center.getX());
                    int yTrans = (int) (centerR.getY() - center.getY());

                    // Add a vector to v proportional to the vector between C and the center of R.
                    movementVector.translate(xTrans < 0 ? -movementFactor : movementFactor,
                            yTrans < 0 ? -movementFactor : movementFactor);

                    // Move R by v.
                    rect.setRect(rect.getX() + movementVector.getX(), rect.getY() + movementVector.getY(),
                            rect.getWidth(), rect.getHeight());

                    // Repeat until nothing overlaps.
                    hasIntersections = true;
                }

            }

            numIterations++;

        }

        System.out.println("That took " + numIterations+ " iterations.");

        Rectangles.this.repaint();

    }

    //find the Bounding rectangle of the list of rectangles
    //by iterating over all rectangles and 
    //finding the top left and bottom right corners
    private Rectangle2D surroundingRect(List<Rectangle2D> rectangles) {

        Point topLeft = null;
        Point bottomRight = null;

        for (Rectangle2D rect : rectangles) {
            if (topLeft == null) {
                topLeft = new Point((int) rect.getMinX(), (int) rect.getMinY());
            } else {
                if (rect.getMinX() < topLeft.getX()) {
                    topLeft.setLocation((int) rect.getMinX(), topLeft.getY());
                }

                if (rect.getMinY() < topLeft.getY()) {
                    topLeft.setLocation(topLeft.getX(), (int) rect.getMinY());
                }
            }

            if (bottomRight == null) {
                bottomRight = new Point((int) rect.getMaxX(), (int) rect.getMaxY());
            } else {
                if (rect.getMaxX() > bottomRight.getX()) {
                    bottomRight.setLocation((int) rect.getMaxX(), bottomRight.getY());
                }

                if (rect.getMaxY() > bottomRight.getY()) {
                    bottomRight.setLocation(bottomRight.getX(), (int) rect.getMaxY());
                }
            }
        }

        return new Rectangle2D.Double(topLeft.getX(), topLeft.getY(), bottomRight.getX() - topLeft.getX(),
                bottomRight.getY() - topLeft.getY());
    }

    //Draws the rectangles in the frame from the rectanglesToDraw data structure  
    public void paintComponent(Graphics g) {
        super.paintComponent(g);
        Graphics2D g2d = (Graphics2D) g;

        for (Rectangle2D entry : rectanglesToDraw) {
            g2d.setStroke(new BasicStroke(1));
            // g2d.fillRect((int) entry.getX(), (int) entry.getY(), (int) entry.getWidth(),
            // (int) entry.getHeight());
            g2d.draw(entry);
        }

    }

    //create GUI components and display it to the user
    protected static void createAndShowGUI() {
        Rectangles rects = new Rectangles();

        rects.reset();

        JFrame frame = new JFrame("Rectangles");
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        frame.setLayout(new BorderLayout());
        frame.add(rects, BorderLayout.CENTER);

        JPanel buttonsPanel = new JPanel();

        JButton fix = new JButton("Fix");

        fix.addActionListener(new ActionListener() {

            @Override
            public void actionPerformed(ActionEvent e) {

                long start = System.currentTimeMillis();
                rects.fix();
                long end = System.currentTimeMillis();

                System.out.println("That took "+TimeUnit.MILLISECONDS.convert(end - start, TimeUnit.MILLISECONDS)+ " ms");

            }
        });

        JButton resetButton = new JButton("Reset");

        resetButton.addActionListener(new ActionListener() {

            @Override
            public void actionPerformed(ActionEvent e) {
                rects.reset();
            }
        });

        buttonsPanel.add(fix);
        buttonsPanel.add(resetButton);

        frame.add(buttonsPanel, BorderLayout.SOUTH);

        frame.setSize(1920, 900);
        frame.setLocationRelativeTo(null);
        frame.setVisible(true);
    }

    public static void main(String[] args) {
        SwingUtilities.invokeLater(new Runnable() {

            @Override
            public void run() {
                createAndShowGUI();

            }
        });
    }

}

Here are a couple of screenshots to illustrate what its doing:

Before:
Before

After:
After


Get this bounty!!!

#StackBounty: #collision-detection #algorithm #tile Tile-based board game collision mechanism algorithm

Bounty: 100

I am looking to see ideas for an algorithm which will handle collisions for some battle-ship tile-based board game.

A little about the game

The game is pretty simple. Basically there is a board, which usually sized 20x36 tiles. One tile is a position that a ship can be at, unless the tile is a rock tile.

Many ships are in the game, and all players have 35 seconds to select 4 moves that their ship will perform. After these 35 seconds, all ships will perform the selected moves parallel, by doing the first selected move, then going to the second, third and fourth, and then 35 seconds again to select new moves.

A ship can either move Forward, Left or Right.

Now these are the collision rules for the game:

  1. All ships that are moving (regardless of direction) attempt to “claim” the space that started directly in front of them. That space has five possibilites:
    a. That space is empty and unclaimed. Then move the ship into that space.
    b. That space contains a stationary ship. Then execute a “bump” (see below).
    c. That space contains a ship that is moving, and claiming the first ship’s space. Then stop movement entirely (with a collision).
    d. That space is empty but claimed by a ship of the same or larger class. Then stop movement entirely (with a collision).
    e. That space is empty but claimed by a ship of smaller class. Then move the ship into that space (with a collision).
  2. All ships that are turning but have not “stopped entirely” then attempt to claim their destination space. Now that space also has five possibilities:

2.a. That space is empty and unclaimed. Then move the ship into that space.

2.b. That space contains a stationary ship OR a ship that moved there in step 1. Then stop movement entirely (with a collision).

2.c. That space contains a ship that is moving, and claiming the first ship’s space. Then stop movement entirely (with a collision).

2.d. That space is empty but claimed by a ship of the same or larger class. Then stop movement entirely (with a collision).

2.e. That space is empty but claimed by a ship of smaller class. Then move the ship into that space (with a collision).
Note: At the end, all ships have their orientation changed if they tried to turn… even if they had “stopped entirely.”
Note that (2b) does not depend on the ship’s class. This allows a small ship to move forward into a tile even if a larger ship is attempting to turn into that tile. If two ships both try to move into the same tile for any other reason, the larger ship succeeds.

Example

So let’s say you select the forward move on your ship, and there is another ship on the target tile you are aiming to (forward). So what do you need to make sure?

You need to check if that target tile is unclaimed. If it’s not unclaimed, you can check if its a rock or another ship. If it is a rock, cancel movement. If it’s another ship, and it does not move, push it by 1 tile and stay in the same location. If that ship does move, you have to ask it if that ship has successfully moved, but for it to return a success message, that other ship has to check if it can move, and that can have a lot of cases with a lot of callbacks and might end up not efficient.

So my question is, how can this be done, in the proper way?

Read more here about the collision mechanism rules


Get this bounty!!!