• # Math for Game Developers: Graphs and Pathfinding

Math and Physics

• Posted By BSVino
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

## User Feedback

Would enjoy more text overview of the video. :(

##### Share on other sites

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 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.

##### Share on other sites

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

???? ?????? ???????? ???????

## Create an account

Register a new account

• ### Game Developer Survey

We are looking for qualified game developers to participate in a 10-minute online survey. Qualified participants will be offered a \$15 incentive for your time and insights. Click here to start!

• 0
• 0
• 0
• 4

• 15
• 21
• 23
• 11
• 25
• ### Similar Content

• Hi guys,
i am trying to implement a simple font renderer using bitmap font texture with a dynamic vertex buffer, i am  able to successfully display text with correct glyph from bitmap texture.
right now i am trying to draw a dynamic string that changes at user input, i.e user able change the displayded text by typing the new one.
The issue is that  length of string is exactly same as what it was initialized with even when updating string at every render frame. string gets updated every fram but is capped at length equal to what is was initialized with.
i am suspecting that vertexBufferDesc.ByteWidth is not getting updated even when i update vertexbuffer by map and unmap it.
initialize
bool GlyphClass::Initialize(ID3D11Device* device, HWND hwnd, int screenWidth, int screenHeight, WCHAR* path) { bool result; m_GlyphWidthData.open("Font/AgencyFBFont_64x64_width.txt"); while (1) { if (m_GlyphWidthData.eof()) { break; } int tmp = 0; m_GlyphWidthData >> tmp; if (tmp != 0) { m_GlyphWidth.push_back(tmp); } } m_GlyphWidthData.close(); m_GlyphCharacter = 'A'; m_StringToDraw = "TEXTTEST@xyz";//userInputString != "" ? userInputString : "VIVEK599 xyz"; m_fontTextureShader = new TextureShaderClass; if (!m_fontTextureShader) { return false; } result = m_fontTextureShader->Initialize(device, hwnd); if (!result) { MessageBox(hwnd, L"Could not initialize font texture shader object!", L"Error", MB_OK); return false; } m_ScreenWidth = screenWidth; m_ScreenHeight = screenHeight; result = InitializeBuffers(device); if (!result) { return false; } result = LoadTexture(device, path); if (!result) { return false; } return true; } updatebuffer
bool GlyphClass::UpdateBuffers(ID3D11DeviceContext* context, int posX, int posY) { m_StringToDraw = userInputString != "" ? userInputString : "STRING 555@xyz0123456789"; VertexType* vertices; D3D11_MAPPED_SUBRESOURCE mappedResource; VertexType* vertexPtr; HRESULT hr; vertices = new VertexType[m_VertexCount * m_StringToDraw.length()]; if (!vertices) { return false; } // Initialize vertex array to zeros at first. memset(vertices, 0, sizeof(VertexType) * m_VertexCount * m_StringToDraw.length() ); float posXOffset = (float)posX; float posYOffset = (float)posY; for ( int i = 0; i < m_StringToDraw.length(); i++ ) { int cx = m_StringToDraw[i] % 16; int cy = m_StringToDraw[i] / 16; float tex_left = (float)cx * (1.f / 16.f); float tex_top = (float)cy * (1.f / 16.f); float tex_right = tex_left + (1.f / 16.f) * ((float)m_GlyphWidth[m_StringToDraw[i]] / 64.f); float tex_bottom = tex_top + (1.f / 16.f); int totalCharWidth = 64; float left = (float)((float)(m_ScreenWidth / 2.f) * -1) + posXOffset; float right = left + (float)m_GlyphWidth[m_StringToDraw[i]]; float top = (float)(m_ScreenHeight / 2.f) - posYOffset; float bottom = top - (float)totalCharWidth; //triangle 1 - clockwise vertices[0 + m_VertexCount * i].position = Vector3(left, top, 0.f); vertices[0 + m_VertexCount * i].texture = Vector2(tex_left, tex_top); vertices[1 + m_VertexCount * i].position = Vector3(right, bottom, 0.f); vertices[1 + m_VertexCount * i].texture = Vector2(tex_right, tex_bottom); vertices[2 + m_VertexCount * i].position = Vector3(left, bottom, 0.f); vertices[2 + m_VertexCount * i].texture = Vector2(tex_left, tex_bottom); //triangle + i 2 vertices[3 + m_VertexCount * i].position = Vector3(left, top, 0.f); vertices[3 + m_VertexCount * i].texture = Vector2(tex_left, tex_top); vertices[4 + m_VertexCount * i].position = Vector3(right, top, 0.f); vertices[4 + m_VertexCount * i].texture = Vector2(tex_right, tex_top); vertices[5 + m_VertexCount * i].position = Vector3(right, bottom, 0.f); vertices[5 + m_VertexCount * i].texture = Vector2(tex_right, tex_bottom); posXOffset += m_GlyphWidth[m_StringToDraw[i]]; } hr = context->Map(m_VertexBuffer, 0, D3D11_MAP_WRITE_DISCARD, 0, &mappedResource); if (FAILED(hr)) { return false; } vertexPtr = (VertexType*)mappedResource.pData; int bufferSize = sizeof(VertexType) * m_VertexCount * m_StringToDraw.length(); memcpy(vertexPtr, (void*)vertices, bufferSize); D3D11_BUFFER_DESC tmpDesc; m_VertexBuffer->GetDesc(&tmpDesc); context->Unmap(m_VertexBuffer, 0); delete[] vertices; vertices = 0; return true; }

• Hello everyone,

I appreciate any help i can get. So i recently started getting this message listed bellow in visual studio when i would compile any game i have for UE4.23.0.

1>EXEC : [1/28] error : Unable to create child process
I have no idea how to fix this, and also i really don't want to have to set all the classes again in a new project.

Second thing is that i can not move my Character on the Sever when testing multiplayer after adding "Role = ROLE_Authority" to sections in an AI Tracker bot class that i created as a part of Tom Loomans Course on Udemy. I am not following Tom Loomans course 100%, Do i need to add sever implementation to my character because i am using different movement code then what Tom uses? I Am happy to share some screen shots if needed.

• I have a very simple question, I am trying to rotate some vertex's around an arbitrary axis. basically I want to use glRotatef and glTranslatef to rotate a space ship I have drawn on the screen. here is my code of my  ship. what it does do is rotate around the origin when I  use the arrow keys left and right.
void drawShip() { glPushMatrix(); glColor3f(255.0f, 0.0f, 0.0f); glTranslatef(-50.0f, 0.0f, 0.0f); glRotatef(rotateship, 0.0f, 0.0f, 1.0f); glBegin(GL_LINE_LOOP); glVertex3f(50.0f, 0.0f, 0.0f); glVertex3f(45.0f, -5.0f, 0.0f); glVertex3f(50.0f, 10.0f, 0.0f); glVertex3f(55.0f, -5.0f, 0.0f); glEnd(); glTranslatef(50.0f, 0.0f, 0.0f); glPopMatrix(); }
• By mujina
What could be a way of avoiding using inheritance and virtual methods when designing components for an entity-component-system?
I'll be more specific about my design issue:
I currently have different classes for different kinds of colliders (let's say, CircleCollider and LineCollider).
My system that checks for collisions and updates the positions and/or velocities of my entities should be something like:
for entity_i in alive_entities { collider_i = get_collider_of_entity(entity_i) // components of same kind are stored contiguously in separate arrays transform_i = get_transform_of_entity(entity_i) for entity_j in alive_entities { collider_j = get_collider_of_entity(entity_j) transform_j = get_transform_of_entity(entity_j) if check_collision(collider_i, collider_j) { update(transform_i) update(transform_j) } } } my problem is that I don't have a generic get_collider_of_entity function, but rather a function get_circle_collider_of_entity and a separate one get_line_collider_of_entity, and so on. (This happens because under the hood I am keeping a mapping (entity_id -> [transform_id, sprite_id, circle_collider_id, line_collider_id, ...]) that tells me whether an entity is using certain kinds of components and which are the indices of those components in the arrays containing the actual components instances. As you can see, each component class is corresponding to a unique index, namely the index position of the array of the mapping described above. For example, transforms are 0, sprites are 1, circle colliders are 2, line colliders are 3, and so on.)
I am in need to write a system as the one in the snippet above. I can write several overloaded check_collision functions that implement the logic for collision detection between different kinds of geometric primitives, but my problem is that I am not sure how to obtain a generic get_collider_of_entity function. I would need something that would get me the collider of an entity, regardless of whether the entity has a circle collider, a line collider, a square collider, etc.
One solution could be to write a function that checks whether in my internal entity_id -> [components_ids] mapping a certain entity has a collider at any of the indices that correspond to colliders. For example, say that the indices related to the collider classes are indices 10 to 20, then my function would do
get_collider_of_entity (entity_id) { for comp_type_id in 10..20{ if mapping[entity_id][comp_type_id] not null { return components_arrays[comp_type_id][entity_id] } } return null } This could turn out to be pretty slow, since I have to do a small search for every collider of every entity. Also, it may not be straightforward to handle returned types here. (I'm working with C++, and the first solution - that is not involving inheritance in any way - would be returning a std::variant<CircleCollider, LineCollider, ... all kinds of components>, since I would need to return something that could be of different types).
Another solution could be having some inheritance among components, e.g. all specific component classes inherit from a base Collider, and overrride some virtual collide_with(const Collider& other) method. Then I would redesign my mapping to probably reserve just one index for colliders, and then I would actual colliders in a polymorphic array of pointers to colliders, instead of having a separate array for CircleColliders, another for LineColliders, and so on. But this would destroy any attempt to be cache-friendly in my design, wouldn't it? That's why I am looking for alternatives.
A third alternative would be to just have a single, only, Collider class. That would internally store the "actual type" ( aka what kind of collider it is ) with dynamic information (like an enum ColliderType). Then I would have all colliders have all members needed by any kind of colliders, and specific collision detection functions which I can dispatch dynamically that only use some of that data. (Practical example: a "Collider" would have a radius, and the coordinate for 2 points, and in case its type was "circle" it would only make use of the radius and of one of the 2 points - used as the center -, while if it was a "segment" it would only make use of the 2 points). My gut feeling is that this would bloat all colliders, and, even if the bloat could be reduced - using unions in some smart way for storing members? I wouldn't know how -, then still the design would be pretty brittle.
I'm clueless and open for ideas and advice! How do you handle in general situations in which you have components that can be naturally modeled as subclasses of a more generic component class? Inheritance? Smart hacks with variants, templates, macros, custom indexing? Dynamic "internal" type?
• By hyyou
In my most complex gameplay source file (single .cpp) with a lot of necessary #include,
... whenever I edit it (e.g. add a single space character), it needs to recompile 40 seconds.