(This is an ongoing series. I’m referring to things I did in the previous installment. If you’re new to this, I recommend starting at the first episode.)

First part of this series | Previous | Next | Index

Now I have kinda-working, kinda-fast algorithm for pathfinding. I could just move on at this point, because this is definitely sufficient for usage, but of course I won’t. While the getThreatBorder() method got second place in resource hogging, it is still too slow for my taste.

Let’s theorycraft a little. The condition for an element to be considered a part of the threat border is to be adjacent to a threatened field, and to have the araId given. Now, I check adjacent tiles, and if i find a threatened one, the algorithm quits. But if I made a note of how many neighbors are threatened , and recorded that… I would get minesweeper. I looked a little into that direction, and while there are great algorithms for it, I doubt they will be more efficient than linear time, which I currently have .

On the array conversion. My problem was that when I’m creating a HashMap of tile numbers per area ids, I don’t know how many tiles will belong to one id beforehand, and I have to specify the array size when creating it. But on the other hand, I can do this once the HashSet of integers is created – if something takes a longer time, but I can do it just once, that’s not a problem. I’m not really constrained on startup, only the onFrame() method is limited in runtime.

		for (Integer i : walkTileNumbersByAreaIdsTemp.keySet()) {
			Object[] objects = walkTileNumbersByAreaIdsTemp.get(i).toArray();
			int[] newArray = new int[objects.length];
			for (int j=0; j<objects.length;j++) {
				newArray[j]= (int) objects[j];
			}
			walkTileNumbersByAreaIds.put(i, newArray);
		}

Apparently there is no built-in way to convert Integer[] to int[]. Oh, well. The getThreatBorder() method works almost out of the box, but i have a problem with this:

    public static void changeWalkTileAreaId(int x, int y, int oldAreaId, int newAreaId) {
        Main.areaDataArray[x][y] = newAreaId;

        int[] tileNumbers = Main.walkTileNumbersByAreaIds.get(oldAreaId);
        if (tileNumbers != null && !tileNumbers.isEmpty()) {
            int dnum = x+y*Main.mapWidthInWalkTiles;
            tileNumbers.remove(x+y*Main.mapWidthInWalkTiles);
        }
        tileNumbers = Main.walkTileNumbersByAreaIds.getOrDefault(newAreaId, new HashSet<>());
        tileNumbers.add(x+y*Main.mapWidthInWalkTiles);
        Main.walkTileNumbersByAreaIds.put(newAreaId, tileNumbers);
    }

Here, the add and remove method of collections is more than convenient. For the same functionality with arrays, I need to resize and re-create them. Argh. So I set out to do that. First, I tried the apache commons ArrayUtils add and remove methods. The results were abysmal, the game slowed to 1-2 FPS. As previously noted, creating new arrays is kinda costly (In the main JPS method, basically that’s what I tried to optimize away).

This did me a bamboozle.

Aren’t these utils supposed to be fast? So I did go deeper and searched for the ArrayUtils source code.

public static <T> T[] removeElement(final T[] array, final Object element) {
        final int index = indexOf(array, element);
        if (index == INDEX_NOT_FOUND) {
            return clone(array);
        }
        return remove(array, index);
    }

I remembered from last time, that there are faster ways to copy an array. Namely, the System.arraycopy() method. Smart people on the Internet already done this. I also needed to take care to not try to remove a nonexisting element, and vice versa, not adding an element that is already present – basically, the functionality of the Set.

    public static void changeWalkTileAreaId(int x, int y, int oldAreaId, int newAreaId) {
        Main.areaDataArray[x][y] = newAreaId;

        int[] tileNumbers = Main.walkTileNumbersByAreaIds.get(oldAreaId);
        if (tileNumbers != null && tileNumbers.length != 0) {
            int dnum = x+y*Main.mapWidthInWalkTiles;
            int index = ArrayUtils.indexOf(tileNumbers,dnum);
            if (index != -1) {
                tileNumbers = Util.removeElement(tileNumbers, index);
            }
        }
        tileNumbers = Main.walkTileNumbersByAreaIds.getOrDefault(newAreaId, new int[0]);
        int dnum = x+y*Main.mapWidthInWalkTiles;

        int index = ArrayUtils.indexOf(tileNumbers,dnum);
        if (index == -1 ) {
            tileNumbers = Util.addElement(tileNumbers, dnum);
        }

        Main.walkTileNumbersByAreaIds.put(newAreaId, tileNumbers);
    }

And eagerly confident in my superiority, I did try this out. I got about 12-13 FPS, which is considerably better, but it is still worse than what I had before. Okay, what seems to be wrong here?

Again, taking a look a the source, I realized this isn’t the library I fall in love with this might be not exactly what I need. What I need is cocaine the first index of an element.

    public static int indexOf(int[] array, int element) {
        for (int i = 0; i<array.length;i++) {
            if (array[i] == element) {
                return i;
            }
        }
        return -1;
    }

Using this did improve the speed, but not by a considerable amount – only 13-15 FPS. I’m starting to think this way is a dead end. My array is unsorted, so binary search is not an option here. And adding sorting will certainly not speed it up. I can’t really speed up either the indexOf(), or the getOrDefault() methods. The getOrDefault() is constant access – hard to improve on that – and the indexOf() will be never be better than linear.

Okay, let’s take a step back, and evaluate our constraints. I’m not really constrained by storage, only execution speed. If I’d have a way to look up things quickly…

The main problem is that I need the ability to look up something quickly, and the ability to group the tiles (or codes of them) by areaId. And beacause of reasons, I need to be able to quickly add/remove ids to/from those groups.

But I don’t need to solve all of those issues with just one data structure.

Nothing preventing me from having a full sized (that is, mapwidth*mapheight) array for every areaId, just for the indexes – where the the nth element is simply a yes/no, and can be interpreted as “Is this element in this areaId group?”. This would eliminate the need for the indexOf() method.

I mean, it would consume a lot of memory, but I actually have an abundance of that. While we are going crazy, I want to check if a two-dimensional, or an one-dimensional array is faster for this. Right of the bat, an 1D array seems like the better choice. But for the lookup, I have to calculate the Ids. As always with this matters, I’m gonna test both.

First, the 1D array approach. Code comprehensibility is starting to suffer somewhat.

//Ok
	public static HashMap<Integer, int[]> walkTileNumberIndexesByAreaIds = new HashMap<>();
//Kinda ok
	HashMap<Integer, HashSet<Integer>> walkTileNumbersByAreaIdsTemp = new HashMap<>();

		for (int x=0; x<areaDataArray.length; x++ ) {
			for (int y = 0; y < areaDataArray[x].length; y++) {
				if (areaDataArray[x][y] == -1) {
					Cartography.mostCommonNeighbor(x,y);
				}
//Not very ok
					HashSet<Integer> t = walkTileNumbersByAreaIdsTemp.getOrDefault(areaDataArray[x][y], new HashSet<>());
					t.add(x + (y * mapWidthInWalkTiles));
				walkTileNumbersByAreaIdsTemp.putIfAbsent(areaDataArray[x][y], t);
			}
		}

		for (Integer i : walkTileNumbersByAreaIdsTemp.keySet()) {
//wat
			Object[] objects = walkTileNumbersByAreaIdsTemp.get(i).toArray();
			int[] indexArray = new int[mapHeightinWalkTiles*mapWidthInWalkTiles];
			int[] newArray = new int[objects.length];
			for (int j=0; j<objects.length;j++) {
//y tho
				newArray[j]= (int) objects[j];
				indexArray[(int) objects[j]] = j;
			}
			walkTileNumbersByAreaIds.put(i, newArray);
			walkTileNumberIndexesByAreaIds.put(i, indexArray);
		}

//And in the Cartography class...
    public static void changeWalkTileAreaId(int x, int y, int oldAreaId, int newAreaId) {
        Main.areaDataArray[x][y] = newAreaId;

        int[] tileNumbers = Main.walkTileNumbersByAreaIds.get(oldAreaId);
        if (tileNumbers != null && tileNumbers.length != 0) {
            int dnum = x+y*Main.mapWidthInWalkTiles;
            //int index = Util.indexOf(tileNumbers,dnum);
            int index = Main.walkTileNumberIndexesByAreaIds.get(oldAreaId)[dnum];
            if (index > 0)
            //if (index != -1) {
                tileNumbers = Util.removeElement(tileNumbers, index);
            Main.walkTileNumberIndexesByAreaIds.get(oldAreaId)[dnum] = -1;
            //}
        }
        tileNumbers = Main.walkTileNumbersByAreaIds.get(newAreaId);

        int dnum = x+y*Main.mapWidthInWalkTiles;
        if (tileNumbers == null) {
            tileNumbers = new int[1];
            tileNumbers[0] = dnum;
        }
        else {
            //int index = Util.indexOf(tileNumbers, dnum);
            int index = Main.walkTileNumberIndexesByAreaIds.get(oldAreaId)[dnum];
            if (index < 0) {
                tileNumbers = Util.addElement(tileNumbers, dnum);
            }
        }
    }

It worked surprisingly well. The FPS hovers around 18-20, but it’s much more steady. With a collection-based approach, I got far more lagspikes. I still get them, but they are less severe, just like my crying outbursts. I think I’ll keep this.

And now, for something completely different.

As in, the 2D array approach, which is basically the same thing, and doesn’t really affect anything. Long story short, it had no noticeable effect – I’ll spare you the code, at this point, I think you can figure it out.

I won’t spare you the red bars though.

The changeWalkTileAreaId() is much faster! It fills me with a sense of not being a complete fuckwit accomplishment, to be honest. When I’m at the point that I’m battling language features for nanosecond gains, it feels somewhat weird.

There are only a few points left to optimize, really. I’ll probably go further down on the “make an array of everything” path, but there isn’t much left to do. The getThreatBorder() is my next target. It checks every neighbor of a given tile, and if any of them is threatened, adds the tile to the threat border. Areas that are examined are continuous, but have an unpredictable shape. There are algorithms for this sort of thing, which I will examine – in the next part.

Thanks for reading! If you liked this article, consider subscribing to the mailing list in the sidebar for updates, or to the RSS feed! Also, if you’d like to support me, my blog, or my podcast,check out my shop here! – I decided to give you free shipping on T-shirts and mugs, just use the code STARCRAFT!