Jump to content
  • Advertisement
  • Remove ads and support GameDev.net for only $3. Learn more: The New GDNet+: No Ads!

  • 06/09/16 01:14 AM
    Sign in to follow this  

    Math for Game Developers: Graphs and Pathfinding

    Math and Physics

    BSVino
    • Posted By BSVino
    Math for Game Developers is exactly what it sounds like - a weekly instructional YouTube series wherein I show you how to use math to make your games. Every Thursday we'll learn how to implement one game design, starting from the underlying mathematical concept and ending with its C++ implementation. The videos will teach you everything you need to know, all you need is a basic understanding of algebra and trigonometry. If you want to follow along with the code sections, it will help to know a bit of programming already, but it's not necessary. You can download the source code that I'm using from GitHub, from the description of each video. If you have questions about the topics covered or requests for future topics, I would love to hear them! Leave a comment, or ask me on my Twitter, @VinoBS
    The video below contains the playlist for all the videos in this series, which can be accessed via the playlist icon at the top of the embedded video frame. The first video in the series is loaded automatically

    Graphs and Pathfinding

    [playlist=PLW3Zl3wyJwWO7p6xpTzs-QR58DRg2Ln0V]


      Report Article
    Sign in to follow this  


    User Feedback


    You had me with the math discussion and the "Kahn Academy" style tutorial.  I think this is a great way to teach this stuff.  But when you started typing in the C++ code and explaining pointers, not using vectors with pointers, using indices for data, and then showing the code in memory, then I felt like you were trying to teach a beginner how to use the language using a Node/Edge data structure as a learning tool.

    Share this comment


    Link to comment
    Share on other sites
    I'm actually a big fan of your videos and I've recommended them to a lot of people in the past to help with understanding complex concepts like quaternions, etc. I think this is the first time I've seen you break to code though (maybe I've only watched ones where you don't), and although you did cover the basics of graphs, it really felt like you could have spent the 'code' time explaining a little bit more about graph basics, or even showing a simple BFS to get from A to B. (This is just referring to the first video in the series here. I'm sure you cover the bases by the end.)

    In any case, Budapest made me lol. I was expecting Byzantium.

    Please keep making videos.

    Share this comment


    Link to comment
    Share on other sites


    Create an account or sign in to comment

    You need to be a member in order to leave a comment

    Create an account

    Sign up for a new account in our community. It's easy!

    Register a new account

    Sign in

    Already have an account? Sign in here.

    Sign In Now

  • Advertisement
  • Advertisement
  • Latest Featured Articles

  • Featured Blogs

  • Popular Now

  • Similar Content

    • By ryt
      I took a look at this video to see the difference between static and dynamic linking. Basically the author uses __declspec(dllexport) to export a function.
      How could we also export classes from the same file? Do we need to put the same keyword before class definition or maybe something else?
    • By ryt
      Consider the following classes and pInt declaration:
      class A { ... }; class B : public A { void function() { int A::*pInt; // use pInt } }; Where does pInt belongs, is it local to B::function() or it's a member of A?
    • By CommanderLake
      I've been experimenting with my own n-body simulation for some time and I recently discovered how to optimize it for efficient multithreading and vectorization with the Intel compiler. It did exactly the same thing after making it multithreaded and scaled very well on my ancient i7 3820 (4.3GHz). Then I changed the interleaved xy coordinates to separate arrays for x and y to eliminate the strided loads to improve AVX scaling and copy the coordinates to an interleaved array for OpenTK to render as points. Now the physics is all wrong, the points form clumps that interact with each other but they are unusually dense and accelerate faster than they decelerate causing the clumps to randomly fly off into the distance and after several seconds I get a NaN where 2 points somehow occupy exactly the same x and y float coordinates. This is the C++ DLL:
      #include "PPC.h" #include <thread> static const float G = 0.0000001F; const int count = 4096; __declspec(align(64)) float pointsx[count]; __declspec(align(64)) float pointsy[count]; void SetData(float* x, float* y){ memcpy(pointsx, x, count * sizeof(float)); memcpy(pointsy, y, count * sizeof(float)); } void Compute(float* points, float* velx, float* vely, long pcount, float aspect, float zoom) { #pragma omp parallel for for (auto i = 0; i < count; ++i) { auto forcex = 0.0F; auto forcey = 0.0F; for (auto j = 0; j < count; ++j) { if(j == i)continue; const auto distx = pointsx[i] - pointsx[j]; const auto disty = pointsy[i] - pointsy[j]; //if(px != px) continue; //most efficient way to avoid a NaN failure const auto force = G / (distx * distx + disty * disty); forcex += distx * force; forcey += disty * force; } pointsx[i] += velx[i] -= forcex; pointsy[i] += vely[i] -= forcey; if (zoom != 1) { points[i * 2] = pointsx[i] * zoom / aspect; points[i * 2 + 1] = pointsy[i] * zoom; } else { points[i * 2] = pointsx[i] / aspect; points[i * 2 + 1] = pointsy[i]; } /*points[i * 2] = pointsx[i]; points[i * 2 + 1] = pointsy[i];*/ } } This is the relevant part of the C# OpenTK GameWindow:
      private void PhysicsLoop(){ while(true){ if(stop){ for(var i = 0; i < pcount; ++i) { velx[i] = vely[i] = 0F; } } if(reset){ reset = false; var r = new Random(); for(var i = 0; i < Startcount; ++i){ do{ pointsx[i] = (float)(r.NextDouble()*2.0F - 1.0F); pointsy[i] = (float)(r.NextDouble()*2.0F - 1.0F); } while(pointsx[i]*pointsx[i] + pointsy[i]*pointsy[i] > 1.0F); velx[i] = vely[i] = 0.0F; } NativeMethods.SetData(pointsx, pointsy); pcount = Startcount; buffersize = (IntPtr)(pcount*8); } are.WaitOne(); NativeMethods.Compute(points0, velx, vely, pcount, aspect, zoom); var pointstemp = points0; points0 = points1; points1 = pointstemp; are1.Set(); } } protected override void OnRenderFrame(FrameEventArgs e){ GL.Clear(ClearBufferMask.ColorBufferBit); GL.EnableVertexAttribArray(0); GL.BindBuffer(BufferTarget.ArrayBuffer, vbo); mre1.Wait(); are1.WaitOne(); GL.BufferData(BufferTarget.ArrayBuffer, buffersize, points1, BufferUsageHint.StaticDraw); are.Set(); GL.VertexAttribPointer(0, 2, VertexAttribPointerType.Float, false, 0, 0); GL.DrawArrays(PrimitiveType.Points, 0, pcount); GL.DisableVertexAttribArray(0); SwapBuffers(); } These are the array declarations:
      private const int Startcount = 4096; private readonly float[] pointsx = new float[Startcount]; private readonly float[] pointsy = new float[Startcount]; private float[] points0 = new float[Startcount*2]; private float[] points1 = new float[Startcount*2]; private readonly float[] velx = new float[Startcount]; private readonly float[] vely = new float[Startcount];  
      Edit 0: It seems that adding 3 zeros to G increases the accuracy of the simulation but I'm at a loss as to why its different without interleaved coordinates. Edit 1: I somehow achieved an 8.3x performance increase with AVX over scalar with the new code above!
    • By DarkRonin
      Hi Guys,
      If your application requires a DLL, is there a way to check that the DLL is present gracefully rather than the typical error that gets thrown?  For example - 'The code execution cannot proceed because xxxxxxxx.dll was not found. Reinstalling the program may fix this problem'.
      In my case the DLL is my own, if that makes any difference.
      Thanks in advance.
       
    • By Acar
      I'm trying to use Assimp to convert a custom format to .FBX. I was abled to export model geometry, bone hierarchy and weights correctly. Rotation of the bones appear to be correct as well.
      My problem is, none of the bones have any translation (0,0,0). So when loaded into Maya, entire bone hierarchy appears as a single dot at the origin. Any ideas as to what I may be doing wrong?
  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!