Better still, a BinaryHeap. (Source in RotT originally courtesy of pjt33 - still coming in useful to this day!)
Cas 
Iāll give both a shot and see what happens.
Any little tiny microsecond of performance I can squeeze out of my pathing is critical, since I have monsters and villagers all over the map (hundreds at a time sometimes) wandering all over the place constantly, and due to game mechanic design/requirements I canāt āput them to sleepā in inactive areas like most games would.
@Rayvolution I donāt know if it would be applicable, but have you looked into faster pathing algorithms like JPS?
http://zerowidth.com/2013/05/05/jump-point-search-explained.html
yeah, I looked into JPS quite a lot a few weeks ago, the problem is my maps donāt actually have any āBlockedā tiles, making JPS not quite work the way itās intended since itās designed to find blocked areas quickly and eliminate bad paths while shooting in the directions of good ones. (and thus, also removing a ton of open tiles by quickly filling large areas on the map). Iām not sure whatāll do in my situation, I think it may actually slow down my performance by opening tons of high-cost nodes very quickly (That would be blocked in a normal map/game) that might not of been touched at all with regular A*, as my A* implementation is fairly good at making straight lines out of those large rooms.
The big problem in my game is that without blocked tiles all mountains and trees end up open nodes instead of closed off/blocked nodes, since they have a terrain cost they need to be part of the Queue, and if I use JPS it may more frequently fill up the queue with those tiles (and leaving them open, slowing down the overall loop).
Itās a complicated problem, because those tiles need to stay open so they can slowly work there way through (in the same way you would figure the cost of moving through tar/mud), so that if pathing fails without going through the mountains or trees itāll already be on itās way to build the shortest path that may involve hacking away at the topography to force itās way to the target.
But, with my current implementation of binarySearch() (or with PriorityQueue/BinaryHeap if Riven and Casās suggestions work out) I donāt think the actual size of the nodeās collection/list will actually impact performance nearly as much as I expected it to when I first looked into JPS. I now sort the ArrayList in descending order with binarySearch() and a custom comparator (lowest on bottom) so the extremely high cost nodes are mostly untouched when a new node is inserted since itāll only push the (usually minimal or non existent) values lower than it to the right. JPS might help out greatly since it wonāt matter nearly as much how large the ArrayList is anymore.
So, tl;dr, I might give it a shot again and see what happens. 
Hmm, sounds tricky. But yeah, if youāre not using a heap/priorityqueue for A*, then there is almost certainly room for improvement right there.
I might slap the tail from this thread on the RPC game thread later. DONE :yawn:
Having said that, binary search is cache trashing galore. Given your access patterns, it might be faster to do a linear search from the tail of the array, or a binary search on the last X elements, if that fails, a binary search on the range before it. In the end memory bandwidth (and cache trashing) is probably your bottleneck, making these quirky, hackish tricks worthwhile.
Everybody knows binary search scales O(log n), but given the characteristics of modern CPUs, it at one point takes a nose dive, once the working set doesnāt fit into cache anymore, and nearly every memory access is a cache miss.
Now, ocourse, this all is meaningless without your current performance numbers, your data models and the characteristics of your mapsā¦ which means weāre mostly making bad assumptions about whatever it is your dealing with.
On that note, if you find out PriorityQueue is a poor fit, and BinaryHeaps seem temptingā¦ keep in mind d-ary heaps (which are like binary heaps, but have d children, where d is a constant, >= 2) which are theoretically slower, but due to better memory management (less cache misses) outperform BinaryHeaps in almost every caseā¦ or so they say.
Have you consided mipmapping your graph?
Generally the most effective optimisation strategy is discarding the majority of your data :persecutioncomplex:
ā¦ or not doing any optimisation at all, if itās actually fast enough and thereās other things to be doing instead 
Cas
Probably wise, weāre way off topic.
yeah, without everyone fulling understanding the system itās hard to offer advice, and itās definitely not a standard system. I think PriorityQueue may be the way to go, since it natively functions the same way Iāve Jerry-rigged my current ArrayList.
Yep, Iāve tried to trim out as much as humanly possible, and only (pre)calculated what was absolutely necessary.
Normally Iād agree, but in this case pathfinding is probably a stress spot in my entire program.
@ Riven - PriorityQueue took a full complex path across the entire map from 55-57ms down to 10-11ms. Awesome!
I think this is where I take Casā advice and consider it fast enough to get the job done. 
Today, I actually had a good sit down this evening and played Retro Pixel Castles for the first time Canāt figure out how to make food! Gah.
While I was playing I had the good sense to profile it, and here is what it produced:
Flat profile of 2278.94 secs (172965 total ticks): main
Interpreted + native Method
0.3% 0 + 258 org.lwjgl.opengl.WindowsDisplay.nGetPbufferCapabilities
0.0% 0 + 41 org.lwjgl.opengl.WindowsContextImplementation.nSwapBuffers
0.0% 0 + 32 org.lwjgl.opengl.WindowsDisplay.nResetDisplayMode
0.0% 0 + 31 java.io.FileOutputStream.close0
0.0% 0 + 30 org.lwjgl.opengl.WindowsDisplay.nSwitchDisplayMode
0.0% 0 + 26 org.lwjgl.opengl.GL11.nglGetFloatv
0.0% 0 + 25 java.net.SocketInputStream.socketRead0
0.0% 0 + 21 java.net.DualStackPlainSocketImpl.connect0
0.0% 0 + 21 org.lwjgl.opengl.EXTFramebufferObject.nglCheckFramebufferStatusEXT
0.0% 0 + 18 sun.nio.ch.FileDispatcherImpl.close0
0.0% 0 + 14 org.lwjgl.opengl.WindowsDisplay.nDestroyWindow
0.0% 0 + 9 org.lwjgl.opengl.GL11.nglGetTexImage
0.0% 1 + 8 org.lwjgl.opengl.GL11.nglGenTextures
0.0% 0 + 9 org.lwjgl.opengl.WindowsPeerInfo.nChoosePixelFormat
0.0% 0 + 8 org.lwjgl.opengl.GL11.nglTexImage2D
0.0% 0 + 7 java.io.RandomAccessFile.close0
0.0% 0 + 7 java.io.WinNTFileSystem.rename0
0.0% 0 + 7 org.lwjgl.openal.AL10.nalBufferData
0.0% 0 + 5 sun.nio.fs.WindowsNativeDispatcher.CreateFile0
0.0% 0 + 5 java.io.WinNTFileSystem.delete0
0.0% 0 + 5 org.lwjgl.opengl.WindowsContextImplementation.nDestroy
0.0% 0 + 4 java.util.zip.ZipFile.close
0.0% 0 + 4 java.net.NetworkInterface.getAll
0.0% 0 + 3 java.io.WinNTFileSystem.getLastModifiedTime
0.0% 0 + 3 java.io.FileInputStream.readBytes
0.8% 75 + 638 Total interpreted (including elided)
Compiled + native Method
0.4% 375 + 0 rpc.particles.ParticleModule.update
0.1% 118 + 2 rpc.entities.EntityModule.getMobType
0.1% 55 + 0 org.newdawn.slick.state.StateBasedGame.update
0.1% 53 + 0 rpc.utilities.PathFinder.searchForResourceTile
0.1% 51 + 0 rpc.entities.EntityBase.updateAnimation
0.1% 43 + 5 rpc.guielements.play.Interface.render
0.0% 43 + 0 rpc.particles.ParticleModule.render
0.0% 36 + 2 rpc.utilities.PathFinder.findPath
0.0% 37 + 0 rpc.entities.EntityBase.combatSearch
0.0% 32 + 2 rpc.particles.ParticleModule.initController
0.0% 25 + 0 rpc.entities.EntityReachMap.buildReachMap
0.0% 23 + 2 rpc.resources.ResourceModule.updateResourceCount
0.0% 20 + 0 org.newdawn.slick.openal.WaveData.convertAudioBytes
0.0% 18 + 1 rpc.entities.EntityBase.updateAI
0.0% 18 + 0 rpc.map.CollisionModule.initController
0.0% 18 + 0 rpc.objects.ObjectRangeBuilder.createSingleRange
0.0% 16 + 0 rpc.BackgroundModule.update
0.0% 13 + 0 rpc.resources.ResourceModule.renderSelection
0.0% 1 + 10 rpc.LightingModule.addLightStraight
0.0% 9 + 1 rpc.ShadowModule.initController
0.0% 7 + 2 rpc.LightingModule.updateLightMap
0.0% 8 + 0 rpc.utilities.PathFinder.searchForEntity
0.0% 7 + 0 rpc.entities.EntityModule.update
0.0% 6 + 0 rpc.entities.essence.EssenceBase.checkTarget
0.0% 5 + 0 rpc.entities.VillagerUtility.getHarvestingWork
1.3% 1119 + 62 Total compiled (including elided)
Stub + native Method
56.6% 0 + 52790 org.lwjgl.opengl.GL11.nglGetFloatv
9.0% 0 + 8399 org.lwjgl.opengl.WindowsContextImplementation.nSwapBuffers
7.9% 0 + 7382 org.lwjgl.opengl.GL11.nglColor4f
5.3% 0 + 4962 org.lwjgl.WindowsSysImplementation.nGetTime
4.4% 0 + 4063 java.lang.Thread.yield
3.9% 0 + 3677 org.lwjgl.opengl.GL11.nglTexCoord2f
3.2% 0 + 2968 java.lang.Thread.sleep
3.0% 0 + 2793 org.lwjgl.opengl.GL11.nglVertex3f
1.0% 0 + 939 org.lwjgl.opengl.GL11.nglEnable
0.8% 0 + 765 org.lwjgl.opengl.GL11.nglTranslatef
0.6% 0 + 528 java.lang.Object.hashCode
0.5% 0 + 434 org.lwjgl.opengl.GL11.nglBegin
0.4% 0 + 375 org.lwjgl.opengl.GL11.nglBindTexture
0.4% 0 + 365 org.lwjgl.opengl.GL11.nglEnd
0.1% 0 + 106 org.lwjgl.opengl.GL11.nglGenTextures
0.1% 0 + 68 java.util.zip.Inflater.inflateBytes
0.1% 0 + 56 org.lwjgl.opengl.GL11.nglCallList
0.1% 0 + 55 org.lwjgl.opengl.GL11.nglPopMatrix
0.1% 0 + 51 java.io.FileInputStream.open0
0.0% 0 + 41 org.lwjgl.opengl.GL11.nglVertex2f
0.0% 0 + 39 org.lwjgl.openal.AL10.nalSourcef
0.0% 0 + 38 org.lwjgl.opengl.GL11.nglLoadIdentity
0.0% 0 + 36 org.lwjgl.opengl.GL11.nglGetError
0.0% 0 + 34 org.lwjgl.opengl.GL11.nglPopClientAttrib
0.0% 0 + 31 org.lwjgl.opengl.GL11.nglDisable
98.0% 6 + 91398 Total stub (including elided)
Thread-local ticks:
46.1% 79665 Blocked (of total)
0.0% 2 Class loader
Global summary of 2278.94 seconds:
100.0% 173043 Received ticks
0.0% 75 Received GC ticks
1.9% 3296 Compilation
0.0% 2 Other VM operations
0.0% 2 Class loader
Note here and there the total lack of any pathfinding code contributing to the CPU usage. In fact notice the total lack of CPU usage. You spend 98% of your time in native code! And half of it is nglGetFloatv, which I canāt for the life of me think why you would ever call it.
Cas
The old pathfinding system is actually pretty solid, it can process 10-15 paths at once in about 15ms, so itās even faster than the new system. It just doesnāt understand terrain movement costs (Itās similar to a Breadth First Search system). As for nglGetFloatv, I honestly have no idea. I donāt call it anywhere in my code, so Iām guessing itās being called under the hood inside Slick2D somewhere. Iāll have to hunt it down, because that has me curious.
Its percentage is probably inflated due to causing a driver stall. The OpenGL function is glGetFloat() BTW.
Line 300 and line 1745, in Graphics.java
public Color getBackground() {
predraw();
FloatBuffer buffer = BufferUtils.createFloatBuffer(16);
@@ GL.glGetFloat(SGL.GL_COLOR_CLEAR_VALUE, buffer);
postdraw();
return new Color(buffer);
}
public void pushTransform() {
predraw();
FloatBuffer buffer;
if (stackIndex >= stack.size()) {
buffer = BufferUtils.createFloatBuffer(18);
stack.add(buffer);
} else {
buffer = (FloatBuffer) stack.get(stackIndex);
}
@@ GL.glGetFloat(SGL.GL_MODELVIEW_MATRIX, buffer);
buffer.put(16, sx);
buffer.put(17, sy);
stackIndex++;
postdraw();
}
most peculiar 
Yeeargh, Slick :point: Keviiiiiiiiiiiiin!
Cas
A small grid might be 256x256=65536 cells. A navigation mesh of the same data might be some like a dozenā¦or maybe even dozens!
Greetings everyone,
For 7 days I will be giving out copies of Retro-Pixel Castles on Twitter. Winners will be announced at the end of each day! Already own a copy? Gift it to a friend!
To enter, simply follow @RaymondDoerr and retweet the current active tweet for that day. This post will be updated daily with latest active tweet, and a list of previous winners. Anyone can enter, names will be collected from the retweet list on twitter, thrown into a (figurative) hat and one name will be picked randomly!
Even if you win, you can even retweet the future active tweets to try your luck for a another copy!
Bonus: Winners Twitter accounts will be listed below, giving your account some free exposure!
CURRENTLY ACTIVE: WEDNESDAY 15TH
Winner be announced early on the 16th just prior to the next tweet!
Winners:
TUESDAY, April 14th - Jon Hearn (@ZenDarklighter)
Upcoming tweets:
THURSDAY, April 16th.
FRIDAY, April 17th.
SATURDAY, April 18th.
SUNDAY, April 19th.
MONDAY, April 20th.
On the latest update ive noticed a few things , firstly the crystal motivator has no image in the menu and it has the same description as the cullus gate. Everything else is great.
I feel as if I need some sort of additions to the game wrt. attacking/defending. Like soldiers and barracks or something.
Cas
Thatās actually what Iām working on right now.
Iām adding heroes to the game (Automated little villagers who canāt work, but defend the village), and the influence tab that will allow you to try to nudge your little guys to do things you want. But by design, it wonāt always work.
Also going to be adding barracks and basic fighters too, although Iām not sure if theyāll make it into this next update.