Chadwyk.com

The ramblings of a developer

Walk boxes and Path finding using A*

This week I spent a few days trying to figure out walk boxes and path finding algorithms, which led to a lot of frustration and wishing that I paid more attention in my freshman CS 367 class on data structures!

After doing a lot of research and finding very little code online to follow, I was finally able to stitch together a prototype that implements walk boxes and path finding!

Walk boxes are polygons that limit the areas that a player can walk in the world.  Path finding is finding the shortest path from a point in Polygon A to a point in polygon Z using those walk boxes to go around obstacles. If you have to walk through several polygons to get to a target, it will return a list of the polygons that has the shortest path.

Here is a really crude example.  Please excuse my horrible Photoshopping skills, but in this image the green arrow is what the algorithm, A* (pronounced A star), would calculate the path of the player should be if they were on A and wanted to get to H. It would then tell me the path should be through polygons A, B, C, D, E, F, G, H.

I found many good articles about the theory behind it, but I couldn’t find much code.  What I could find, wasn’t written in C++. The other issue was that a lot of the articles were written for a simplified version of A* using a grid system. This would be great if I was making a tile based game like Lumps of Clay or Super Mario Brothers, but it doesn’t really help much when it comes to polygons / nodes.

In the end I found a wonderful article written by Julian Ceipek. http://jceipek.com/Olin-Coding-Tutorials/pathing.html It describes path finding much better than I ever could.  It also describes in detail the  algorithm to find the shortest path between two nodes.  Perfect! That’s precisely what I wanted.  But the little code he had was written in another language.

It took a while but I was able to make my own node / graph class to store the node and edge data.  Then I was able to port his code over to C++ to analyze the graph data to find the shortest path between nodes. It seems to be working after some tweaks.

Now I need to find some time to implement the algorithm, “Simple Stupid Funnel”.  It is a smoothing algorithm which makes the path taken more direct instead of having the player walk to the center of each polygon before moving on to the next.

 

Without further ado, a short demo!

 

Published by chadwyk on | Permalink

Point and Click!

For the past few days, I have been playing around with Cocos2d-x.  It is a bit different than Cocos2d-iphone, but very similar so I know the concepts.  I just need to figure out the correct syntax since a lot of the old classes have been deprecated.

 

Anyways, I have started a framework with a GUI for the buttons for the verbs.  When you click them, it also updates the label on the cursor, and when hovering over objects it will update the label to say for example, “Open door”.

 

Tonight I got working the player animations and movements.  You can click around on the screen and the player character will follow the points that you clicked.

 

It’s slowly coming together, but of course a lot more to do!

 

It is very basic, but here is a quick sample video of what I’ve done.  The graphics are temporary and taken from a free site.

Published by chadwyk on | Permalink

Changing direction to Cocos2d-x

So I know I was really excited to create my own engine from scratch, but I fear at this point in time it is just way too far over my head.  I’ve spent the last several days trying to get SDL or OpenGL to load and display images, with limited success. Once I get an image loaded, I’m unable to really abstract it into a class to load multiple instances.  If I was able to, it wouldn’t be very efficient either because I’d need to figure out how to do texture atlases and texture batching, as well figure a way to manage the textures in memory.  It’s all really complex to someone that hasn’t touched c++ in a long time.

 

At the moment I feel fairly defeated, so instead, for now, since someone has already done all the hard work, I think I’m going abandon my engine attempt and try out Cocos2d-x instead.  It is a C++ version of the Cocos2d-iphone engine which I used to make Lumps of Clay.  It should be fairly similar I think.  Since Cocos2d-x is written in C++ it is cross platform compatible, and I believe the renderer uses OpenGL at the core, but it’s super easy to load images as Cocos2d-x does all the hard work for you .  I just don’t know how compatible it will be if I ever want to port it to devices like the Nintendo Switch. But if the Switch will be incompatible with Cocos2d-x, it would probably be incompatible with my custom engine since they were both going to be OpenGL based.

 

Maybe I’ll try to make a simple game with it, then send my pitch to Nintendo so I can get a Developer Kit, then see how hard it would be to port it.  We’ll see.  For now, I’m going to abandon my own engine and try to get a prototype going this weekend in Cocos2d-x.

 

In the future I can always revisit my own engine project.

 

UPDATE

I hopped on the forum for cocos2d-x and there is a thread about supporting the Switch since it was revealed that the Switch supports OpenGL.  It appears that at least one developer was able to port their game to the Switch from cocos2d-x, so that is good news!  There was not any posts lately on it so I left one asking if anyone else had been able to port to Switch.  Hoping to hear back some positive results!

Published by chadwyk on | Permalink

Early Roadblock

So… It turns out, loading graphics is hard!

 

My goal is to be able to make a basic texture loader class that I can use on any node class in my engine.  This is kind of how Cocos2d-iPhone worked, in a simplified manner.  If I could only find one that was already created someplace that I could utilize…

I was able to get SDL to load images, though it was pretty complicated, and not optimized what-so-ever yet.  Plus if I go this route, I can’t use cool lighting effects.

I think my preferred route is to use OpenGL for that purpose.  However, I started playing with OpenGL and that’s waaaay harder then using SDL.  Though there are some image libraries that are supposed to make it easier.  I am currently trying one called SOIL, but I can’t find much documentation on it at all and the last time it was updated was years ago.  I might look at trying out a different one and seeing if I can get it working with OpenGL.

 

 

Published by chadwyk on | Permalink

The Beginnings of a Game Engine

Over the past 2 nights, I have been researching and watching tutorials on SDL and OpenGL.  So far I believe I have the beginnings of a game engine.  It is starting to feel a bit like a very primitive version of the Cocos2d-iphone engine, which is my goal because that is what I am used to.

 

It is really basic, but so far I have it opening an SDL window, then instantiating OpenGL as the renderer.  I have an event handler class created to detect key presses or mouse clicks.  I am able to draw a basic OpenGL polygon using shaders and move it via keystrokes.  I was able to create a scene manager with different scenes so I can have a menu scene, game scene, etc. I also created a resource manager which can load files into memory.

 

Like I said it’s all super basic stuff, but I’m actually really fascinated by how it all fits together.  Previously I just used other engines that other people created.  Now I’m getting a better idea how it all works.

 

The internal debate I’m having is using the OpenGL renderer or SDL.  SDL is good for 2d graphics, but is lower performance due to not talking to the hardware directly.  OpenGL does do that, but it is more complicated and difficult to learn, but I can do more with it like lighting effects and particles.  It also has a good chance of not working with console ports in the future.  I’m hoping that I would be able to switch it out with a different renderer if I ever get a chance to port it to Nintendo, Playstation, or Xbox.

 

My next steps are to get it to load textures so I can display images so I can start to do meaningful things instead of just a blue square. Then I’d like to figure out how to do scene transitions – fade out / in, etc. I also need to verify that they remove from memory properly when switching.

 

All in all, this project is still exciting me and for not touching c++ in years, I feel like things are coming along great!

Published by chadwyk on | Permalink