Been redoing the path generation code (I love redoing stuff, NOT). Previously I generated the path from the nodes themselves. Looking for neighbouring nodes and calculate the distance between them based on their midpoint and then get the G, H, F values for the a-star pathfinder. The nodes are basically connected polygons. This turns out to be a bad idea if two nodes are connected by a number of other nodes... consider this example:
The green path is generated by searching the nodes and performing distance calculation by their centers. This is bad since it always will generate the same path no matter where the NPC is standing in the node. He could be standing at the south part of the left node and wanting to go to the other south part of the right node. In that case the corridor at the bottom would be the best path to take. This can be achieved by searching the gates between the nodes instead of the nodes themselves. I didn't realize this would become a problem until I had finished the algorithm :/ So now I am doing the searches on the gates themselves and comparing distances using the gates centers. I have also noticed that the path can become a bit strange if I evaluate the H-component (H component = the estimated movement cost to move from that given node to the final destination). I guess it is due to that I am using a navigation mesh and not a fixed sized grid. I fixed it by not account for the H component.
As the new year has arrived I wanted to celebrate this. I have therefore released Apple Catcher for free for a limited time. You can find Apple Catcher in the App Store or by following this iTunes link. Hope you enjoy this small game! :-)
A short post... I've recently thought about how I want the walls to look in the game and I have come to the decision that I want them to be black on the topside. Up until now the walls have had their topside the same color as their sides. I think by coloring the topside black it will add to the feeling that there actually is a roof that can't be seen. Here's a picture showing how it could look like.
A follow-up on the last post, an SWF video showing the path finding in action. This is not how the finished game (Space Patrol 3000) will look or feel but it shows some concepts of the technology.
The player guy walks around a test level, finding the shortest path between rooms. The algorithm could use some adjustments so that he directly goes to path points that are reachable instead of walking to every existing point in the correct order. At the end of the video some serious crate pushing can be seen, this is achieved using bullet physics.
I'm very happy I've gotten this far with the actual game without quitting on the project =)
Well, I got some new fancy lines showing the path. It was more work than I expected it to be. The trouble laid in adding points to the path where the nodes connect. Here's a picture showing what I am talking about:
The lower image has two blue segments that are created at the node intersections. These extra segments might not be very useful in this particular example but when the map has long corridors and thick walls you want to avoid the path taking too narrow corners. If it did it would cause the bot or player to walk against the walls of the corridor.
To accomplish this I had to make the winding of the node polygons the same. if didn't I could end up with something like this:
Notice the intersection is all zig-zag. This is because the new segment points have been turned in the opposite direction due to polygon winding.
So I fixed my polygon winding by using Newell's surface normal method and a dotproduct between this node normal and a vector pointing down on the map. The dotproduct result told me which way the node was winded (result <0 or >=0). Well I thought this would solve my zig-zag problem, it didn't. I still had zig-zags on some segments and I could not figure out why. Well, until I sat about four hours thinking about it hehe. It turns out that I still could get my segments reversed if they crossed the polygon begin<->end points. As an example, If I built a line from these indexes it would be okay:
4,5,6,7,8
would result in a line between points 4 and 8. A segment built using these points would not be okay:
6,7,8,0,1,2
that would result in a line beginning on 6 and end on 2.. i.e. bad winding. So I just had to check whether the end and start point was added in the wrong order. if they were, swap the lines two points.
Hello again!
Thought it was time to update the journal. I haven't had so much time to spend on development but I have nonetheless managed to get the navigation mesh and a-star tools working. The picture below shows a mesh edited with the new tool. The blue path is generated by A-star.
Next I am going to try to generate a spline curve to show the actual path, not just the nodes concerned.
Hello, http://www.oddgames.com has had an overhaul. The outside might look a lot like the old site but behind the scenes there is a whole new deal :) I have redesigned the entire site and it is now built upon a CMS (in my case WordPress). This allows for such things as comments, online editing of the news items, news categories etc... I have also set up a phpbb based forum which I am very pleased with. In the upcoming days I plan to create a page for nimrod. I hadn’t done it yet because I felt that the site wasn’t what it should have been and the page would have to be remade. Well, you can visit the site on the above link.
Regarding the editor, I am still implementing the navigation mesh. Left to do is the saving and loading routines. You can now break and weld individual vertices in the mesh (very neat!).
Posted - 2/8/2010 9:36:02 AM
